计算几何

OI&ACM, 数学
  1. 1 【cogs 896】圈奶牛
  2. 2 【bzoj 1007】[HNOI2008]水平可见直线
  3. 3 【bzoj 1610】[Usaco2008 Feb]Line连线游戏
  4. 4 【bzoj 2300】[HAOI2011]防线修建
  5. 5 【bzoj 2618】[Cqoi2006]凸多边形
  6. 6 【poj 2187】Beauty Contest
  7. 7 【poj 3608】Bridge Across Islands

1 【cogs 896】圈奶牛

给出点的坐标，计算最短的能够围住这些点的围栏的长度。

裸凸包 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<algorithm>
#include<cstdio>
#include<cmath> 
using namespace std;
int n; double ans;
struct node{
	double x,y;
}a[10001],b[10001];
double dis(node aa,node bb)
{return sqrt((aa.x-bb.x)*(aa.x-bb.x)+(aa.y-bb.y)*(aa.y-bb.y));}
double Cross(node aa,node bb,node cc)
{return (aa.x-cc.x)*(bb.y-cc.y)-(bb.x-cc.x)*(aa.y-cc.y);}
bool cmp(node aa,node bb)
{
	double t=Cross(aa,bb,a[1]);
	return (!t)?dis(aa,a[1])<dis(bb,a[1]):t>0;
}
void Graham()
{
	int k=1,top=0;
	for(int i=2;i<=n;i++)
	  if((a[k].y>a[i].y)||(a[k].y==a[i].y&&a[k].x>a[i].x)) k=i;
	if(k!=1) swap(a[1],a[k]);
	sort(a+2,a+n+1,cmp);
	for(int i=1;i<=n;i++)
	{
		while(top>1&&Cross(a[i],b[top],b[top-1])>=0) top--;
		b[++top]=a[i];
	}
	b[++top]=a[1];
	for(int i=1;i<top;i++) ans+=dis(b[i],b[i+1]);
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	  scanf("%lf%lf",&a[i].x,&a[i].y);
	Graham();
	printf("%.2lf",ans);
}

2 【bzoj 1007】[HNOI2008]水平可见直线

在xoy直角坐标平面上有n条直线L1,L2,...Ln,若在y值为正无穷大处往下看,能见到Li的某个子线段,则称Li为可见的,否则Li为被覆盖的.
例如,对于直线:
L1:y=x; L2:y=-x; L3:y=0
则L1和L2是可见的,L3是被覆盖的.
给出n条直线,表示成y=Ax+B的形式(|A|,|B|<=500000),且n条直线两两不重合.求出所有可见的直线.

有点像半平面交 假设逆时针排序，则如果交点在上一个交点左边，则把上一条边删掉
x和y交点的横坐标=(y.b-x.b)/(x.a-b.a);
我把两边分母乘过去就没有浮点数了，2333

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<algorithm>
#include<cstdio>
using namespace std;
int n,st[50005],top,yes[50005];
struct node{ int a,b,num; } l[50005];
bool cmp(const node &x,const node &y) { x.a<y.a; }
bool OK(int x,int y,int z)
{
	if(l[x].a==l[y].a) return l[x].b>l[y].b;
	if(!z) return 0;
	return (long long)(l[y].b-l[x].b)*(l[y].a-l[z].a)<=(long long)(l[z].b-l[y].b)*(l[x].a-l[y].a);
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	  scanf("%d%d",&l[i].a,&l[i].b),l[i].num=i;
	sort(l+1,l+n+1,cmp);
	for(int i=1;i<=n;i++)
	{
		while(top&&OK(i,st[top],st[top-1])) top--;
		st[++top]=i;
	}
	for(int i=1;i<=top;i++) yes[l[st[i]].num]=1;
	for(int i=1;i<=n;i++) if(yes[i]) printf("%d ",i);
}

3 【bzoj 1610】[Usaco2008 Feb]Line连线游戏

有一块画着N (2 <= N <= 200)个不重合的点的木板，可以选两个点画一条过它们的直线，当且仅当平面上不存在与画出直线平行的直线。
求最大总条数

排个序去个重就行了吧 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<algorithm>
#include<cstdio>
using namespace std;
int n,m,ans,x[201],y[201];
struct node{
	int x,y;
}a[20000];
bool cmp(const node &a,const node &b)
{
	if(!a.x||!b.x) return b.x;
	if(a.x*b.x>0) return a.y*b.x<a.x*b.y;
	return a.y*b.x>a.x*b.y;
	//return (double)a.y/a.x<(double)b.y/b.x;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&x[i],&y[i]);
		for(int j=1;j<i;j++)
		  a[++m].x=x[i]-x[j],a[m].y=y[i]-y[j];
	}
	sort(a+1,a+m+1,cmp);
	for(int i=1;i<=m;i++)
	  if(i==1||a[i].y*a[i-1].x!=a[i].x*a[i-1].y) ans++;
	printf("%d\n",ans);
}

4 【bzoj 2300】[HAOI2011]防线修建

有删点的凸包

我自己想了一个在线的做法，2333 不要吐槽慢
删点时，对答案有影响当且仅当这个点在凸包上
如果在，则删掉这个的和前后两点之间的边，然后在前后两点之间做一次凸包

正解好像是离线，不停加边，用set维护 by CXC

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
int n,m,top,Q,num[100005],pre[100005],next[100005];
double ans;
struct node{
	int x,y,id,no;
}a[100005],b[100005];
int Cross(node a,node b,node c)
{	return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y);   }
double dis(node a,node b)
{   return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));   }
bool cmp(const node &aa,const node &bb)
{
	int t=Cross(aa,bb,a[1]);
	return (!t)?dis(aa,a[1])<dis(bb,a[1]):t<0;
}
void Graham(int st,int ed)
{
	top=0;
	for(int i=st;i<=ed;i++)
	  if(!a[i].no)
	  {
	  	while(top>1&&Cross(a[i],b[top],b[top-1])<=0) top--;
	  	b[++top]=a[i];b[top].id=i;
	  }
	for(int i=1;i<top;i++) 
	{
		next[b[i].id]=b[i+1].id;
		pre[b[i+1].id]=b[i].id;
		ans+=dis(b[i],b[i+1]);
	}  
}
int main()
{
	scanf("%d%d%d%d",&n,&a[2].x,&a[2].y,&m);
	a[3].x=n;m+=3;
	for(int i=4;i<=m;i++)
	  scanf("%d%d",&a[i].x,&a[i].y),a[i].id=i-3;
	sort(a+2,a+m+1,cmp);
	for(int i=1;i<=m;i++)
	  if(a[i].id) num[a[i].id]=i;
	Graham(1,m);
	scanf("%d",&Q);
	for(int i=1,k,t;i<=Q;i++)
	{
		scanf("%d",&k);
		if(k==1)
		{
			scanf("%d",&t);t=num[t];
			a[t].no=1;
			if(!pre[t]||!next[t]) continue;
			ans-=dis(a[t],a[pre[t]])+dis(a[t],a[next[t]]);
			Graham(pre[t],next[t]);pre[t]=next[t]=0;
		}
		else printf("%.2lf\n",ans);
	}
}

5 【bzoj 2618】[Cqoi2006]凸多边形

求几个凸多边形的交集面积

半平面交 求交点：（不要吐槽我把x轴画到了O上。。。） k1=(b.b-a.a)*(a.b-a.a) 即三角形ACD的面积
k2=(a.b-a.a)*(b.a-a.a) 即三角形ABC的面积
∴ S△ACD/S△ABC = DF/BE = OF/OE = OH/OG = k1/k2
∴ OG = GH * k1/(k1+k2)
∴ O的坐标就求出来了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
int n,cnt,tot;
struct node1 {   double x,y;   }  p[55],a[505];
struct node2 {   node1 a,b; double k;   }  l[505],q[505];
node1 operator -(node1 a,node1 b)
{   node1 t;t.x=a.x-b.x;t.y=a.y-b.y;return t;   }
double operator *(node1 a,node1 b)
{   return a.x*b.y-a.y*b.x;   }
bool operator <(node2 a,node2 b)
{   return a.k==b.k?(a.b-a.a)*(b.b-a.a)<0:a.k<b.k;   }
node1 Inter(node2 a,node2 b)
{
	double k1,k2,t;
	k1=(b.b-a.a)*(a.b-a.a);
	k2=(a.b-a.a)*(b.a-a.a);
	t=k1/(k1+k2);
	node1 ans;
	ans.x=b.b.x+(b.a.x-b.b.x)*t;
	ans.y=b.b.y+(b.a.y-b.b.y)*t;
	return ans;
}
bool jud(node2 a,node2 b,node2 c)
{
	return (c.b-c.a)*(Inter(a,b)-c.a)<0;
}
double calc()
{
	sort(l+1,l+cnt+1);
	int L=1,R=0;
	for(int i=1;i<=cnt;i++)
	  if(l[i].k!=l[i-1].k) l[++tot]=l[i];
	for(int i=1;i<=tot;i++)
	{
		while(L<R&&jud(q[R-1],q[R],l[i])) R--;
		while(L<R&&jud(q[L+1],q[L],l[i])) L++;
		q[++R]=l[i];
	}
	while(L<R&&jud(q[R-1],q[R],l[L])) R--;
	while(L<R&&jud(q[L+1],q[L],l[R])) L++;
	q[R+1]=q[L];tot=0;
	for(int i=L;i<=R;i++) a[++tot]=Inter(q[i],q[i+1]);
	a[++tot]=a[1];
	if(tot<3) return 0;
	double ans=0;
	for(int i=1;i<=tot;i++) ans+=a[i]*a[i+1];
	return fabs(ans)/2;
}
int main()
{
	scanf("%d",&n);
	for(int i=1,k;i<=n;i++)
	{
		scanf("%d",&k);
		for(int j=1;j<=k;j++) scanf("%lf%lf",&p[j].x,&p[j].y);
		p[k+1]=p[1];
		for(int j=1;j<=k;j++) l[++cnt].a=p[j],l[cnt].b=p[j+1];
	}
	for(int i=1;i<=cnt;i++)
	  l[i].k=atan2(l[i].b.y-l[i].a.y,l[i].b.x-l[i].a.x);
	printf("%.3lf",calc());
}

6 【poj 2187】Beauty Contest

求最远点对距离

旋转卡(qia)壳 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
int n,top;
struct node{
	int x,y;
}a[50005],b[50005];
node operator -(node a,node b)
{
	node t;
	t.x=a.x-b.x;t.y=a.y-b.y;
	return t;
}
int operator *(node a,node b)
{
	return a.x*b.y-a.y*b.x;
}
int dis(node a,node b)
{
	return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
bool operator <(node aa,node bb)
{
	int t=(aa-a[1])*(bb-a[1]);
	return (!t)?dis(aa,a[1])<dis(bb,a[1]):t>0;
}
void Graham()
{
	int k=1;
	for(int i=2;i<=n;i++)
	  if(a[i].x<a[k].x||(a[i].x==a[k].x)&&a[i].y<a[k].y) k=i;
	if(k!=1) swap(a[k],a[1]);
	sort(a+2,a+n+1);
	for(int i=1;i<=n;i++)
	{
		while(top>1&&(a[i]-b[top-1])*(b[top]-b[top-1])>=0) top--;
		b[++top]=a[i];
	}
	b[top+1]=b[1];
}
int Calc()
{
	int q=2,ans=0;
	for(int i=1;i<=top;i++)
	{
		while((b[i+1]-b[i])*(b[q+1]-b[i])>(b[i+1]-b[i])*(b[q]-b[i]))
		  q=q%top+1;
		ans=max(ans,dis(b[q],b[i]));
	}
	return ans;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);
	Graham();
	printf("%d\n",Calc());
}

7 【poj 3608】Bridge Across Islands

求两个凸多边形的最近距离

旋转卡壳
想了好久一直不会写。。。
其实就是一条边在旋，另一个点找面积最小的（根据gcx的证明，应该能保证取到距离最短）
然后更新答案
然而我调了一下午，2333，因为平行时没有更新Q+1。。。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
#define eps 1e-10
using namespace std;
struct node{ double x,y; }a[10005],b[10005],t;
double ans; 
double dis(node a,node b)
{
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double Cross(node a,node b,node c)
{
	return (a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x);
}
double Dot(node a,node b,node c)
{
	return (a.x-c.x)*(b.x-c.x)+(a.y-c.y)*(b.y-c.y);
}
bool cmp(node aa,node bb)
{
	double k=Cross(aa,bb,t);
	return (!k)?dis(aa,t)<dis(bb,t):k>0;
}
void Sort(node *a,int n)
{
	int k=1;
	for(int i=2;i<=n;i++) if((a[k].y>a[i].y)||(a[k].y==a[i].y&&a[k].x>a[i].x)) k=i;
	t=a[k];
	sort(a+1,a+n+1,cmp);
}
void Add(node x,node y,node z)
{
	if(Dot(z,y,x)/dis(x,z)/dis(x,y)<-eps) ans=min(ans,dis(x,z));
	else if(Dot(x,z,y)/dis(y,z)/dis(x,y)<-eps) ans=min(ans,dis(y,z));
	else ans=min(ans,fabs(Cross(z,y,x))/dis(x,y));
}
void Calc(node *a,node *b,int n,int m)
{
	int P=1,Q=1;
	for(int i=1;i<=n;i++)  if(a[i].y<a[P].y) P=i;
	for(int i=1;i<=m;i++)  if(b[i].y>b[Q].y) Q=i;
 	for(int i=1,t;i<=n;i++)
	{
		while(Cross(b[Q+1],a[P+1],a[P])-Cross(b[Q],a[P+1],a[P])<-eps) Q=Q%m+1;
		Add(a[P],a[P+1],b[Q]);
		if(Cross(b[Q+1],a[P+1],a[P])-Cross(b[Q],a[P+1],a[P])<eps) Add(a[P],a[P+1],b[Q+1]);
		P=P%n+1;
	}
}
int main()
{
	int n,m;
	while(scanf("%d%d",&n,&m)&&n)
	{
		ans=30000;
		for(int i=1;i<=n;i++)  scanf("%lf%lf",&a[i].x,&a[i].y); 
		for(int i=1;i<=m;i++)  scanf("%lf%lf",&b[i].x,&b[i].y);
		Sort(a,n);Sort(b,m);
		a[n+1]=a[1];b[m+1]=b[1];
		Calc(a,b,n,m);Calc(b,a,m,n);
		printf("%.6lf\n",ans);
	}
}

计算几何