计算几何

  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

计算几何基础 by sui

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);
}
}