【算法笔记】计算几何题目总结

  • 本文为博主原创，未经许可不得转载

入门题目

【UVa11178】Morley定理

由于对称性，我们只需要知道如何求点D即可

首先计算角ABC的值a，然后把射线BC逆时针旋转a/3得到直线BD，同样的可得直线CD

然后计算BD和CD的交就行了

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
#include<bits/stdc++.h>
#define FILE "read"
#define eps 1e-6
using namespace std;
inline int read(){
	int x=0,f=1;  char ch=getchar();
	while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
	while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
struct Point{
	double x,y;
	Point(double a=0,double b=0):x(a),y(b){}
	inline void read(){scanf("%lf%lf",&x,&y);}
	inline void print(){printf("%.6lf %.6lf ",x,y);}
	inline Point operator+(const Point &b){return Point(x+b.x,y+b.y);}
	inline Point operator-(const Point &b){return Point(x-b.x,y-b.y);}
	inline Point operator*(const double p){return Point(x*p,y*p);}
	inline Point operator/(const double p){return Point(x/p,y/p);}
	inline bool operator==(const Point &b){return fabs(x-b.x)<eps&&fabs(y-b.y)<eps;}
	inline Point rotate(double rad){return Point(x*cos(rad)-y*sin(rad),x*sin(rad)+y*cos(rad));}
};
inline double Dot(Point A,Point B){return A.x*B.x+A.y*B.y;}
inline double Lenth(Point A){return sqrt(Dot(A,A));}
inline double Angle(Point A,Point B){return acos(Dot(A,B)/Lenth(A)/Lenth(B));}
inline double Cross(Point A,Point B){return A.x*B.y-B.x*A.y;}
inline Point Intersection(Point P,Point v,Point Q,Point w){return P+v*(Cross(w,P-Q)/Cross(v,w));}
Point get(Point A,Point B,Point C){
	Point v1=C-B;
	double rad=Angle(A-B,v1);
	v1=v1.rotate(rad/3);
	Point v2=B-C;
	rad=Angle(A-C,v2);
	v2=v2.rotate(-rad/3);
	return Intersection(B,v1,C,v2);
}
void solve(){
	Point A,B,C;
	A.read(); B.read(); C.read();
	Point D=get(A,B,C);
	Point E=get(B,C,A);
	Point F=get(C,A,B);
	D.print();E.print();F.print();
	puts("");
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	for(int T=read();T;--T) solve();
	return 0;
}

　　

　　

【CF772#B】不稳定的风筝

我们先思考一个这样的问题：多边形在什么情况下会变相交？

如图所示，A、B、C是多边形上的连续顶点，我们看到，只要直径超过B到AC的距离，就会出现多边形自交的情况

所以我们只需要对于连续的三个顶点，求出其中一点到另外两点所成直线的距离，更新答案就行了

注意：INF不要开小

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
#include<bits/stdc++.h>
#define FILE "read"
#define INF 1e12
#define cmin(a,b) a=min(a,b)
#define cmax(a,b) a=max(a,b)
using namespace std;
struct Point{
	double x,y;
	Point(double a=0,double b=0):x(a),y(b){}
	inline void read(){scanf("%lf%lf",&x,&y);}
	inline Point operator+(const Point &b){return Point(x+b.x,y+b.y);}
	inline Point operator-(const Point &b){return Point(x-b.x,y-b.y);}
	inline Point operator*(const double p){return Point(x*p,y*p);}
	inline Point operator/(const double p){return Point(x/p,y/p);}
}A[1050];
inline double Dot(Point A,Point B){return A.x*B.x+A.y*B.y;}
inline double Cross(Point A,Point B){return A.x*B.y-A.y*B.x;}
inline double Lenth(Point A){return sqrt(Dot(A,A));}
inline double dis(Point A,Point B,Point C){return fabs(Cross(B-A,C-A))/Lenth(B-C);}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	int n; scanf("%d",&n); double ans=INF;
	for(int i=1;i<=n;++i) A[i].read(); A[++n]=A[1]; A[++n]=A[2];
	for(int i=2;i<n;++i){
		cmin(ans,dis(A[i+1],A[i],A[i-1]));
		cmin(ans,dis(A[i],A[i+1],A[i-1]));
		cmin(ans,dis(A[i-1],A[i],A[i+1]));
	}
	printf("%.10lf\n",ans/2);
	return 0;
}

　　

　　

【LA3263】好看的一笔画

首先介绍欧拉公式：设平面图的顶点数、边数、面数分别为$V$、$E$、$F$，则有$V+F-E=2$

所以我们只需要计算出顶点数和边数就行了

注意计算线交后要去重，因为可能出现多线共点的情况

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
#include<bits/stdc++.h>
#define FILE "read"
#define eps 1e-6
#define MAXN 90100
using namespace std;
struct Point{
	double x,y;
	Point(double a=0,double b=0):x(a),y(b){}
	inline void read(){scanf("%lf%lf",&x,&y);}
	inline Point operator+(const Point &b){return Point(x+b.x,y+b.y);}
	inline Point operator-(const Point &b){return Point(x-b.x,y-b.y);}
	inline Point operator*(const double p){return Point(x*p,y*p);}
	inline Point operator/(const double p){return Point(x/p,y/p);}
	inline bool operator==(const Point &b)const{return fabs(x-b.x)<eps&&fabs(y-b.y)<eps;}
	inline bool operator< (const Point &b)const{return x<b.x||(x==b.x&&y<b.y);}
}A[MAXN],P[MAXN];
int n,CASE,V,E;
double Dot(Point A,Point B){return A.x*B.x+A.y*B.y;}
double Cross(Point A,Point B){return A.x*B.y-B.x*A.y;}
int dcmp(double x){
	if(fabs(x)<eps) return 0;
	else return x<0?-1:1;
}
bool Segment_Jiao(Point A,Point B,Point C,Point D){
	return dcmp(Cross(B-A,C-A)*Cross(B-A,D-A))<0&&dcmp(Cross(D-C,A-C)*Cross(D-C,B-C))<0;
}
bool On_Segment(Point P,Point A,Point B){
	return dcmp(Cross(A-P,B-P))==0&&dcmp(Dot(A-P,B-P))<0;
}
Point Line_Jiao(Point P,Point v,Point Q,Point w){
	Point u=P-Q;
	double t=Cross(w,u)/Cross(v,w);
	return P+v*t;
}
void solve(){
	V=0; E=n-1;
	for(int i=1;i<=n;++i) A[i].read();
	for(int i=1;i<n;++i) P[++V]=A[i];
	for(int i=1;i<n;++i)for(int j=i+1;j<n;++j)if(Segment_Jiao(A[i],A[i+1],A[j],A[j+1]))
		P[++V]=Line_Jiao(A[i],A[i+1]-A[i],A[j],A[j+1]-A[j]);
	sort(P+1,P+V+1);V=unique(P+1,P+V+1)-(P+1);
	for(int i=1;i<=V;++i)for(int j=1;j<n;++j)if(On_Segment(P[i],A[j],A[j+1]))++E;
	printf("Case %d: There are %d pieces.\n",++CASE,E+2-V);
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	while(scanf("%d",&n)!=EOF&&n)solve();
	return 0;
}

　　

　　

【UVa11796】狗的距离

首先看一种简化的情况：甲和乙的线路都是直线，那么根据相对运动理论，可看成甲静止不动，乙沿着直线走，即计算点到直线的最大最小距离即可

然后我们只需要模拟整个过程，处理每个拐点的情况即可

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
66
67
68
69
70
71
#include<bits/stdc++.h>
#define FILE "read"
#define eps 1e-6
#define INF 1e9
#define cmin(a,b) a=min(a,b)
#define cmax(a,b) a=max(a,b)
using namespace std;
int n,m,CASE;
double v1,v2,maxx,minn;
inline int read(){
	int x=0,f=1;  char ch=getchar();
	while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
	while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
inline int dcmp(double x){
	if(fabs(x)<eps) return 0;
	else return x<0?-1:1;
}
struct Point{
	double x,y;
	Point(double a=0,double b=0):x(a),y(b){}
	inline void read(){scanf("%lf%lf",&x,&y);}
	inline Point operator+(const Point &b){return Point(x+b.x,y+b.y);}
	inline Point operator-(const Point &b){return Point(x-b.x,y-b.y);}
	inline Point operator*(const double p){return Point(x*p,y*p);}
	inline Point operator/(const double p){return Point(x/p,y/p);}
	inline bool operator==(const Point &b){return fabs(x-b.x)<eps&&fabs(y-b.y)<eps;}
}A[55],B[55];
inline double Dot(Point A,Point B){return A.x*B.x+A.y*B.y;}
inline double Cross(Point A,Point B){return A.x*B.y-A.y*B.x;}
inline double Lenth(Point A){return sqrt(Dot(A,A));}
inline double Segment_Dis(Point P,Point A,Point B){
	if(A==B) return Lenth(P-A);
	else if(dcmp(Dot(B-A,P-A))<0) return Lenth(P-A);
	else if(dcmp(Dot(A-B,P-B))<0) return Lenth(P-B);
	else return fabs(Cross(A-B,P-B)/Lenth(A-B));
}
void updata(Point P,Point A,Point B){
	cmin(minn,Segment_Dis(P,A,B));
	cmax(maxx,Lenth(P-A));
	cmax(maxx,Lenth(P-B));
}
void solve(){
	n=read();  m=read();  v1=v2=0;
	for(int i=1;i<=n;++i) A[i].read();
	for(int i=1;i<=m;++i) B[i].read();
	for(int i=1;i<n;++i) v1+=Lenth(A[i+1]-A[i]);
	for(int i=1;i<m;++i) v2+=Lenth(B[i+1]-B[i]);
	int Sa=1,Sb=1;  Point Pa=A[1],Pb=B[1];
	minn=INF;  maxx=-INF;
	while(Sa<n&&Sb<m){
		double La=Lenth(A[Sa+1]-Pa);
		double Lb=Lenth(B[Sb+1]-Pb);
		double T=min(La/v1,Lb/v2);
		Point Va=(A[Sa+1]-Pa)/La*T*v1;
		Point Vb=(B[Sb+1]-Pb)/Lb*T*v2;
		updata(Pa,Pb,Pb+Vb-Va);
		Pa=Pa+Va;
		Pb=Pb+Vb;
		if(Pa==A[Sa+1])  ++Sa;
		if(Pb==B[Sb+1])  ++Sb;
	}
	printf("Case %d: %.0lf\n",++CASE,maxx-minn);
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	for(int T=read();T;--T) solve();
	return 0;
}

　　

　　

　　

凸包

【UVa10652】包装木板

直接求凸包的面积即可

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
#include<bits/stdc++.h>
#define FILE "read"
#define eps 1e-6
#define MAXN 2510
using namespace std;
const double pi=acos(-1);
int n,cnt;
inline int read(){
	int x=0,f=1;  char ch=getchar();
	while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
	while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
struct Point{
	double x,y;
	Point(double a=0,double b=0):x(a),y(b){}
	inline void read(){scanf("%lf%lf",&x,&y);}
	inline void print(){printf("%.2lf %.2lf\n",x,y);}
	inline Point operator+(const Point &b){return Point(x+b.x,y+b.y);}
	inline Point operator-(const Point &b){return Point(x-b.x,y-b.y);}
	inline Point operator*(const double p){return Point(x*p,y*p);}
	inline Point operator/(const double p){return Point(x/p,y/p);}
	inline bool operator< (const Point &b)const {return x<b.x||(x==b.x&&y<b.y);}
	inline bool operator==(const Point &b)const {return fabs(x-b.x)<eps&&fabs(y-b.y)<eps;}
	inline Point rotate(double rad){return Point(x*cos(rad)-y*sin(rad),x*sin(rad)+y*cos(rad));}
}A[MAXN],q[MAXN];
inline double Cross(Point A,Point B){return A.x*B.y-A.y*B.x;}
int ConvexHull(){
	int tail=0;
	sort(A+1,A+cnt+1);
	for(int i=1;i<=cnt;++i){
		while(tail>1&&Cross(q[tail]-q[tail-1],A[i]-q[tail-1])<=0) --tail;
		q[++tail]=A[i];
	}
	int lim=tail;
	for(int i=cnt-1;i;--i){
		while(tail>lim&&Cross(q[tail]-q[tail-1],A[i]-q[tail-1])<=0) --tail;
		q[++tail]=A[i];
	}
	return tail;
}
void solve(){
	n=read();  double area=0,ans=0;  cnt=0;
	for(int i=1;i<=n;++i){
		double x,y,w,h,j;
		scanf("%lf%lf%lf%lf%lf",&x,&y,&w,&h,&j);
		Point O(x,y);  double rad=-j*pi/180;
		A[++cnt]=O+Point(w/2,h/2).rotate(rad);
		A[++cnt]=O+Point(w/2,-h/2).rotate(rad);
		A[++cnt]=O+Point(-w/2,h/2).rotate(rad);
		A[++cnt]=O+Point(-w/2,-h/2).rotate(rad);
		area+=w*h;
	}
	int tot=ConvexHull()-1;
	for(int i=2;i<tot;++i) ans+=Cross(q[i]-q[1],q[i+1]-q[1])/2;
	printf("%.1lf %%\n",area/ans*100);
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	for(int T=read();T;--T) solve();
	return 0;
}

　　

　　

【LA2453】围墙

先求凸包，然后答案就是凸包周长+$2\pi L$

为什么是$2\pi L$呢？这个问题留个读者画图思考

另外这题卡输出格式，23333

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
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 1010
#define eps 1e-6
#define INF 1e9
using namespace std;
const double pi=acos(-1);
struct Point{
	double x,y;
	Point(double a=0,double b=0):x(a),y(b){}
	inline void read(){scanf("%lf%lf",&x,&y);}
	inline void print(){printf("%.2lf %.2lf",x,y);}
	inline Point operator+(const Point &b){return Point(x+b.x,y+b.y);}
	inline Point operator-(const Point &b){return Point(x-b.x,y-b.y);}
	inline Point operator*(const double p){return Point(x*p,y*p);}
	inline Point operator/(const double p){return Point(x/p,y/p);}
	inline bool operator==(const Point &b)const{return fabs(x-b.x)<eps&&fabs(y-b.y)<eps;}
	inline bool operator< (const Point &b)const{return x<b.x||(x==b.x&&y<b.y);}
}A[MAXN],q[MAXN];
int n,L;
inline int read(){
	int x=0,f=1;  char ch=getchar();
	while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
	while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
inline double Dot(Point A,Point B){return A.x*B.x+A.y*B.y;}
inline double Cross(Point A,Point B){return A.x*B.y-A.y*B.x;}
void solve(){
	n=read();  L=read();  double ans=0;
	for(int i=1;i<=n;++i) A[i].read();
	sort(A+1,A+n+1);  int tail=0;
	for(int i=1;i<=n;++i){
		while(tail>1&&Cross(q[tail]-q[tail-1],A[i]-q[tail-1])<=0) --tail;
		q[++tail]=A[i];
	}
	int lim=tail;
	for(int i=n-1;i;--i){
		while(tail>lim&&Cross(q[tail]-q[tail-1],A[i]-q[tail-1])<=0) --tail;
		q[++tail]=A[i];
	}
	for(int i=1;i<tail;++i) ans+=sqrt(Dot(q[i+1]-q[i],q[i+1]-q[i]));
	ans+=pi*L*2;
	printf("%.0lf\n",ans);
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	int T=read();
	while(T--){
		solve();
		if(T) puts("");
	}
	return 0;
}

　　

　　

【UVa11168】飞机场

求出点的凸包之后，我们不难发现，选择凸包的边所在的直线一定比选择其它直线更优

所以我们只需要枚举凸包上的直线，然后我们可以在$O(1)$的时间内求出总距离

设直线的一般式为$Ax+By+C$，然后使用公式$d=\frac{|Ax_0+By_0+C|}{\sqrt {A^2+B^2}}$

我们只需要预处理所有横坐标的和、所有纵坐标的和就行了

至于把两点式化为一般式，那就脑洞大开随便做了

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
66
67
68
69
#include<bits/stdc++.h>
#define FILE "read"
#define eps 1e-6
#define INF 1e9
#define MAXN 10100
#define cmin(a,b) a=min(a,b)
#define cmax(a,b) a=max(a,b)
using namespace std;
double sumx,sumy,ans;
int n,CASE; 
inline int read(){
	int x=0,f=1;  char ch=getchar();
	while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
	while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
struct Point{
	double x,y;
	Point(double a=0,double b=0):x(a),y(b){}
	inline void read(){scanf("%lf%lf",&x,&y);}
	inline void print(){printf("%.2lf %.2lf\n",x,y);}
	inline Point operator+(const Point &b){return Point(x+b.x,y+b.y);}
	inline Point operator-(const Point &b){return Point(x-b.x,y-b.y);}
	inline Point operator*(const double p){return Point(x*p,y*p);}
	inline Point operator/(const double p){return Point(x/p,y/p);}
	inline bool operator==(const Point &b)const{return fabs(x-b.x)<eps&&fabs(y-b.y)<eps;}
	inline bool operator< (const Point &b)const{return x<b.x||(x==b.x&&y<b.y);}
}A[MAXN],q[MAXN];
inline double Cross(Point A,Point B){return A.x*B.y-A.y*B.x;}
int ConvexHull(){
	int tail=0;
	sort(A+1,A+n+1);
	for(int i=1;i<=n;++i){
		while(tail>1&&Cross(q[tail]-q[tail-1],A[i]-q[tail-1])<=0) --tail;
		q[++tail]=A[i];
	}
	int lim=tail;
	for(int i=n-1;i;--i){
		while(tail>lim&&Cross(q[tail]-q[tail-1],A[i]-q[tail-1])<=0) --tail;
		q[++tail]=A[i];
	}
	return tail;
}
void updata(Point A,Point B){
	double a,b,c;
	if(A.x==B.x) cmin(ans,fabs(sumx-n*A.x));
	else{
		double k=(A.y-B.y)/(A.x-B.x),temp=A.y-k*A.x;
		a=k; b=-1; c=temp;
		double ret=fabs(a*sumx+b*sumy+c*n)/sqrt(a*a+b*b);
		cmin(ans,ret);
	}
}
void solve(){
	n=read();  ans=INF;  sumx=sumy=0;
	for(int i=1;i<=n;++i) A[i].read();
	for(int i=1;i<=n;++i) sumx+=A[i].x;
	for(int i=1;i<=n;++i) sumy+=A[i].y;
	if(n==1||n==2) {printf("Case #%d: %.3lf\n",++CASE,(double)0);return;}
	int tot=ConvexHull();
	for(int i=1;i<tot;++i) updata(q[i],q[i+1]);
	printf("Case #%d: %.3lf\n",++CASE,ans/n);
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	for(int T=read();T;--T) solve();
	return 0;
}

　　

　　

【UVa10256】点集划分

先求出红点的凸包和蓝点的凸包，那么我们判断这两个凸包是否相离即可

具体的话就是要判断：

(1)任取两凸包上的线段没有交点

(2)任取凸包上一点，该点不在另一凸包内

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<bits/stdc++.h>
#define FILE "read"
#define eps 1e-6
#define MAXN 510
using namespace std;
struct Point{
	double x,y;
	Point(double a=0,double b=0):x(a),y(b){}
	inline void read(){scanf("%lf%lf",&x,&y);}
	inline void print(){printf("%.2lf %.2lf\n",x,y);}
	inline Point operator+(const Point &b){return Point(x+b.x,y+b.y);}
	inline Point operator-(const Point &b){return Point(x-b.x,y-b.y);}
	inline Point operator*(const double p){return Point(x*p,y*p);}
	inline Point operator/(const double p){return Point(x/p,y/p);}
	inline bool operator==(const Point &b)const {return fabs(x-b.x)<eps&&fabs(y-b.y)<eps;}
	inline bool operator< (const Point &b)const {return x<b.x||(x==b.x&&y<b.y);}
}A[MAXN],B[MAXN],q[5][MAXN];
int n,m,tail[5];
inline double Dot(Point A,Point B){return A.x*B.x+A.y*B.y;}
inline double Cross(Point A,Point B){return A.x*B.y-A.y*B.x;}
inline int dcmp(double x){
	if(fabs(x)<eps) return 0;
	else return x<0?-1:1;
}
inline bool Segment_Jiao(Point A,Point B,Point C,Point D){
	return dcmp(Cross(B-A,C-A)*Cross(B-A,D-A))<0&&dcmp(Cross(D-C,A-C)*Cross(D-C,B-C))<0;
}
inline bool On_Segment(Point P,Point A,Point B){
	return dcmp(Cross(P-A,P-B))==0&&dcmp(Dot(P-A,P-B))<0;
}
inline bool Check1(Point P){
	int wn=0;
	for(int i=1;i<tail[2];++i){
		if(On_Segment(P,q[2][i],q[2][i+1])) return 1;
		int k=dcmp(Cross(q[2][i+1]-q[2][i],P-q[2][i]));
		int d1=dcmp(q[2][i].y-P.y);
		int d2=dcmp(q[2][i+1].y-P.y);
		if(k>0&&d1<=0&&d2>0) ++wn;
		if(k<0&&d2<=0&&d1>0) --wn;
	}
	return wn?1:0;
}
inline bool Check2(Point P){
	int wn=0;
	for(int i=1;i<tail[1];++i){
		if(On_Segment(P,q[1][i],q[1][i+1])) return 1;
		int k=dcmp(Cross(q[1][i+1]-q[1][i],P-q[1][i]));
		int d1=dcmp(q[1][i].y-P.y);
		int d2=dcmp(q[1][i+1].y-P.y);
		if(k>0&&d1<=0&&d2>0) ++wn;
		if(k<0&&d2<=0&&d1>0) --wn;
	}
	return wn?1:0;
}
void solve(){
	for(int i=1;i<=n;++i) A[i].read();
	for(int i=1;i<=m;++i) B[i].read();
	tail[1]=tail[2]=0;  int flag=1;
	sort(A+1,A+n+1);  sort(B+1,B+m+1);
	for(int i=1;i<=n;++i){
		while(tail[1]>1&&Cross(q[1][tail[1]]-q[1][tail[1]-1],A[i]-q[1][tail[1]-1])<=0) --tail[1];
		q[1][++tail[1]]=A[i];
	}
	int lim=tail[1];
	for(int i=n-1;i;--i){
		while(tail[1]>lim&&Cross(q[1][tail[1]]-q[1][tail[1]-1],A[i]-q[1][tail[1]-1])<=0) --tail[1];
		q[1][++tail[1]]=A[i];
	}
	for(int i=1;i<=m;++i){
		while(tail[2]>1&&Cross(q[2][tail[2]]-q[2][tail[2]-1],B[i]-q[2][tail[2]-1])<=0) --tail[2];
		q[2][++tail[2]]=B[i];
	}
	lim=tail[2];
	for(int i=m-1;i;--i){
		while(tail[2]>lim&&Cross(q[2][tail[2]]-q[2][tail[2]-1],B[i]-q[2][tail[2]-1])<=0) --tail[2];
		q[2][++tail[2]]=B[i];
	}
	for(int i=1;i<tail[1];++i)for(int j=1;j<tail[2];++j)if(Segment_Jiao(q[1][i],q[1][i+1],q[2][j],q[2][j+1]))flag=0;
	for(int i=1;i<tail[1];++i)if(Check1(q[1][i]))flag=0;
	for(int i=1;i<tail[2];++i)if(Check2(q[2][i]))flag=0;
	if(flag) puts("Yes");
	else puts("No");
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	while(scanf("%d%d",&n,&m)!=EOF&&n&&m) solve();
	return 0;
}

　　

　　

　　

半平面交

【POJ3130】数学家的难题

半平面交经典应用：判断多线性核的存在性

把多边形的边看成半平面，只需要判断交是否为空就行了

吐个槽：POJ居然不支持bits库

这道题曾出现在Pku科技营上，当时naive不会计算几何没有做出来

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<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cmath>
#include<algorithm>
#define FILE "read"
#define MAXN 105
#define eps 1e-6
#define INF 1e9
using namespace std;
struct Point{
	double x,y;
	Point(double a=0,double b=0):x(a),y(b){}
	inline void read(){scanf("%lf%lf",&x,&y);}
	inline void print(){printf("%.2lf %.2lf\n",x,y);}
	inline Point operator+(const Point &b){return Point(x+b.x,y+b.y);}
	inline Point operator-(const Point &b){return Point(x-b.x,y-b.y);}
	inline Point operator*(const double p){return Point(x*p,y*p);}
	inline Point operator/(const double p){return Point(x/p,y/p);}
	inline bool operator==(const Point &b)const{return fabs(x-b.x)<eps&&fabs(y-b.y)<eps;}
	inline bool operator< (const Point &b)const{return x<b.x||(x==b.x&&y<b.y);}
}A[MAXN],P[MAXN];
struct Line{
	Point P,v;  double ang;  Line(){}
	Line(Point A,Point B):P(A),v(B){ang=atan2(v.y,v.x);}
	inline bool operator< (const Line &b)const{return ang<b.ang;}
}L[MAXN],q[MAXN];
int n;
inline double Cross(Point A,Point B){return A.x*B.y-A.y*B.x;}
inline bool On_Left(Point A,Line L){return Cross(L.v,A-L.P)>0;}
inline Point Line_Jiao(Line A,Line B){
	Point u=A.P-B.P;
	double t=Cross(B.v,u)/Cross(A.v,B.v);
	return A.P+A.v*t;
}
bool check(){
	sort(L+1,L+n);  int head=1,tail=0;  q[++tail]=L[1];
	for(int i=2;i<n;++i){
		while(head<tail&&!On_Left(P[tail-1],L[i])) --tail;
		while(head<tail&&!On_Left(P[head],L[i])) ++head;
		q[++tail]=L[i];
		if(fabs(q[tail].ang-q[tail-1].ang)<eps){
			--tail;
			if(On_Left(L[i].P,q[tail]))  q[tail]=L[i];
		}
		if(head<tail) P[tail-1]=Line_Jiao(q[tail-1],q[tail]);
	}
	while(head<tail&&!On_Left(P[tail-1],q[head])) --tail;
	return tail-head>1;
}
void solve(){
	for(int i=1;i<=n;++i) A[i].read(); A[++n]=A[1];
	for(int i=1;i<n;++i)  L[i]=Line(A[i],A[i+1]-A[i]);
	if(check()) puts("1");
	else puts("0");
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	while(scanf("%d",&n)!=EOF&&n) solve();
	return 0;
}

　　

　　

【LA2512】艺术画廊

半平面交经典应用：求多边形核的存在区域面积

求出半平面交后算面积就行了

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
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 2010
#define eps 1e-6
#define INF 1e9
using namespace std;
struct Point{
	double x,y;
	Point(double a=0,double b=0):x(a),y(b){}
	inline void read(){scanf("%lf%lf",&x,&y);}
	inline void print(){printf("%.2lf %.2lf\n",x,y);}
	inline Point operator+(const Point &b){return Point(x+b.x,y+b.y);}
	inline Point operator-(const Point &b){return Point(x-b.x,y-b.y);}
	inline Point operator*(const double p){return Point(x*p,y*p);}
	inline Point operator/(const double p){return Point(x/p,y/p);}
	inline bool operator==(const Point &b)const{return fabs(x-b.x)<eps&&fabs(y-b.y)<eps;}
	inline bool operator< (const Point &b)const{return x<b.x||(x==b.x&&y<b.y);}
}A[MAXN],P[MAXN];
struct Line{
	Point P,v;  double ang;  Line(){}
	Line(Point A,Point B):P(A),v(B){ang=atan2(v.y,v.x);}
	inline bool operator< (const Line &b)const{return ang<b.ang;}
}L[MAXN],q[MAXN];
int n;
inline int read(){
	int x=0,f=1;  char ch=getchar();
	while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
	while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
inline double Cross(Point A,Point B){return A.x*B.y-A.y*B.x;}
inline bool On_Left(Point A,Line L){return Cross(L.v,A-L.P)>0;}
inline Point Line_Jiao(Line A,Line B){
	Point u=A.P-B.P;
	double t=Cross(B.v,u)/Cross(A.v,B.v);
	return A.P+A.v*t;
}
void solve(){
	n=read();for(int i=n;i;--i)A[i].read();
	for(int i=1;i<n;++i)L[i]=Line(A[i],A[i+1]-A[i]);  L[n]=Line(A[n],A[1]-A[n]);
	int head=1,tail=0; sort(L+1,L+n+1); q[++tail]=L[1];
	for(int i=2;i<=n;++i){
		while(head<tail&&!On_Left(P[tail-1],L[i])) --tail;
		while(head<tail&&!On_Left(P[head],L[i])) ++head;
		q[++tail]=L[i];
		if(fabs(q[tail].ang-q[tail-1].ang)<eps){
			--tail;
			if(On_Left(L[i].P,q[tail])) q[tail]=L[i];
		}
		if(head<tail) P[tail-1]=Line_Jiao(q[tail],q[tail-1]);
	}
	P[tail]=Line_Jiao(q[tail],q[head]);
	while(head<tail&&!On_Left(P[tail-1],q[head])) --tail;
	double ans=0;
	for(int i=head+1;i<tail;++i) ans+=Cross(P[i]-P[head],P[i+1]-P[head])/2;
	printf("%.2lf\n",ans);
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	for(int T=read();T;--T) solve();
	return 0;
}

　　

　　

【UVa10084】更冷更热

首先很显然的是：如果出现了“Same”，之后的答案就是0，这个要记得特判掉

然后没加入一个条件，就相当于增加了一个半平面：它的中垂线

求一下半平面交，然后计算面积即可

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
66
67
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 1010
#define eps 1e-6
#define INF 1e9
using namespace std;
const double pi=acos(-1);
struct Point{
	double x,y;
	Point(double a=0,double b=0):x(a),y(b){}
	inline Point operator+(const Point &b){return Point(x+b.x,y+b.y);}
	inline Point operator-(const Point &b){return Point(x-b.x,y-b.y);}
	inline Point operator*(const double p){return Point(x*p,y*p);}
	inline Point operator/(const double p){return Point(x/p,y/p);}
	inline bool operator==(const Point &b)const{return fabs(x-b.x)<eps&&fabs(y-b.y)<eps;}
	inline bool operator< (const Point &b)const{return x<b.x||(x==b.x&&y<b.y);}
	inline Point rotate(double rad){return Point(x*cos(rad)-y*sin(rad),x*sin(rad)+y*cos(rad));}
}A[MAXN],P[MAXN];
struct Line{
	Point P,v; double ang; Line(){}
	Line(Point A,Point B):P(A),v(B){ang=atan2(v.y,v.x);}
	inline bool operator< (const Line &b)const{return ang<b.ang;}
}L[MAXN],q[MAXN];
int n,cnt,tot,flag;
char ch[10];
inline double Cross(Point A,Point B){return A.x*B.y-A.y*B.x;}
inline bool On_Left(Point A,Line L){return Cross(L.v,A-L.P)>0;}
inline Point Half(Point A,Point B){return Point((A.x+B.x)/2,(A.y+B.y)/2);}
inline Point Line_Jiao(Line A,Line B){
	Point u=A.P-B.P;
	double t=Cross(B.v,u)/Cross(A.v,B.v);
	return A.P+A.v*t;
}
void solve(){
	scanf("%s",ch);  if(ch[0]=='S') flag=1;
	if(flag) {puts("0.00"); return;}
	if(ch[0]=='C') L[++tot]=Line(Half(A[cnt],A[cnt-1]),(A[cnt]-A[cnt-1]).rotate(pi/2));
	else L[++tot]=Line(Half(A[cnt],A[cnt-1]),(A[cnt]-A[cnt-1]).rotate(pi*3/2));
	sort(L+1,L+tot+1); int head=1,tail=0; q[++tail]=L[1];
	for(int i=2;i<=tot;++i){
		while(head<tail&&!On_Left(P[tail-1],L[i])) --tail;
		while(head<tail&&!On_Left(P[head],L[i])) ++head;
		q[++tail]=L[i];
		if(fabs(q[tail].ang-q[tail-1].ang)<eps){
			--tail;
			if(On_Left(L[i].P,q[tail])) q[tail]=L[i];
		}
		if(head<tail) P[tail-1]=Line_Jiao(q[tail],q[tail-1]);
	}
	while(head<tail&&!On_Left(P[tail-1],q[head])) --tail;
	P[tail]=Line_Jiao(q[tail],q[head]);
	if(tail-head<1) {puts("0.00"); return;}
	double ans=0;
	for(int i=head+1;i<tail;++i) ans+=Cross(P[i]-P[head],P[i+1]-P[head])/2;
	printf("%.2lf\n",ans);  cnt++;
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	L[++tot]=Line(Point(0,0),Point(1,0));
	L[++tot]=Line(Point(10,0),Point(0,1));
	L[++tot]=Line(Point(10,10),Point(-1,0));
	L[++tot]=Line(Point(0,10),Point(0,-1));
	A[cnt++]=Point(0,0);
	while(scanf("%lf%lf",&A[cnt].x,&A[cnt].y)!=EOF)solve();
	return 0;
}

　　

　　

【LA3890】离海最远的点

我们先二分一个答案，然后把多边形缩一缩，判断半平面交是否非空即可

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
66
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 205
#define eps 1e-8
#define INF 1e9
using namespace std;
struct Point{
	double x,y;
	Point(double a=0,double b=0):x(a),y(b){}
	inline void read(){scanf("%lf%lf",&x,&y);}
	inline void print(){printf("%.2lf %.2lf\n",x,y);}
	inline Point operator+(const Point &b){return Point(x+b.x,y+b.y);}
	inline Point operator-(const Point &b){return Point(x-b.x,y-b.y);}
	inline Point operator*(const double p){return Point(x*p,y*p);}
	inline Point operator/(const double p){return Point(x/p,y/p);}
	inline bool operator==(const Point &b)const{return fabs(x-b.x)<eps&&fabs(y-b.y)<eps;}
	inline bool operator< (const Point &b)const{return x<b.x||(x==b.x&&y<b.y);}
}A[MAXN],P[MAXN];
struct Line{
	Point P,v;  double ang;  Line(){} 
	Line(Point P,Point v):P(P),v(v){ang=atan2(v.y,v.x);}
	inline bool operator< (const Line &b)const{return ang<b.ang;}
}L[MAXN],q[MAXN];
int n;
inline double Dot(Point A,Point B){return A.x*B.x+A.y*B.y;}
inline double Cross(Point A,Point B){return A.x*B.y-A.y*B.x;}
inline double Lenth(Point A){return sqrt(Dot(A,A));}
inline Point Normal(Point A){return Point(-A.y/Lenth(A),A.x/Lenth(A));}
inline bool On_Left(Point A,Line L){return Cross(L.v,A-L.P)>0;}
inline Point Line_Jiao(Line A,Line B){
	Point u=A.P-B.P;
	double t=Cross(B.v,u)/Cross(A.v,B.v);
	return A.P+A.v*t;
}
bool check(double mid){
	for(int i=1;i<n;++i) L[i]=Line(A[i]+Normal(A[i+1]-A[i])*mid,A[i+1]-A[i]);
	sort(L+1,L+n);  int head=1,tail=0; q[++tail]=L[1];
	for(int i=2;i<n;++i){
		while(head<tail&&!On_Left(P[tail-1],L[i])) --tail;
		while(head<tail&&!On_Left(P[head],L[i])) ++head;
		q[++tail]=L[i];
		if(fabs(q[tail].ang-q[tail-1].ang)<eps){
			--tail;
			if(On_Left(L[i].P,q[tail])) q[tail]=L[i];
		}
		if(head<tail) P[tail-1]=Line_Jiao(q[tail-1],q[tail]);
	}
	while(head<tail&&!On_Left(P[tail-1],q[head])) --tail;
	return tail-head>1;
}
void solve(){
	for(int i=1;i<=n;++i) A[i].read(); A[++n]=A[1];
	double l=0,r=INF;
	while(l+eps<r){
		double mid=(l+r)/2;
		if(check(mid)) l=mid;
		else r=mid;
	}
	printf("%.6lf\n",l);
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	while(scanf("%d",&n)!=EOF&&n) solve();
	return 0;
}

　　

　　

【LA2218】铁人三项

这题思路很妙啊

设比赛总长度为$k$(常数)，其中游泳长度为$x$，自行车为$y$，赛跑为$k-x-y$

则选手i能打败选手j的条件为：$\frac{x}{v_i}+\frac{y}{u_i}+\frac{k-x-y}{w_i}<\frac{x}{v_j}+\frac{y}{u_j}+\frac{k-x-y}{w_j}$

整理为$Ax+By+C>0$的形式，则

$A=(\frac{k}{v_j}-\frac{k}{w_j})+(\frac{k}{v_i}-\frac{k}{w_i})$

$B=(\frac{k}{u_j}-\frac{k}{w_j})+(\frac{k}{u_i}-\frac{k}{w_i})$

$C=\frac{k}{w_j}-\frac{k}{w_i}$

这相当于一个半平面，至于打败所有人，就相当于求所有半平面的交

注意：由于精度问题，常数k建议设置为10000，且需要特判3个速度都大于/小于另一个选手的情况

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
66
67
68
69
70
71
72
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 205
#define eps 1e-6
#define INF 1e9
using namespace std;
const double chty=1e4;//常数
struct Point{
	double x,y;
	Point(double a=0,double b=0):x(a),y(b){}
	inline Point operator+(const Point &b){return Point(x+b.x,y+b.y);}
	inline Point operator-(const Point &b){return Point(x-b.x,y-b.y);}
	inline Point operator*(const double p){return Point(x*p,y*p);}
	inline Point operator/(const double p){return Point(x/p,y/p);}
	inline bool operator==(const Point &b)const{return fabs(x-b.x)<eps&&fabs(y-b.y)<eps;}
	inline bool operator< (const Point &b)const{return x<b.x||(x==b.x&&y<b.y);}
}A[MAXN],P[MAXN];
struct Line{
	Point P,v; double ang; Line(){}
	Line(Point A,Point B):P(A),v(B){ang=atan2(v.y,v.x);}
	inline bool operator< (const Line &b)const{return ang<b.ang;}
}L[MAXN],q[MAXN];
double v[MAXN],u[MAXN],w[MAXN];
int n;
inline double Cross(Point A,Point B){return A.x*B.y-A.y*B.x;}
inline bool On_Left(Point A,Line L){return Cross(L.v,A-L.P)>0;}
inline Point Line_Jiao(Line A,Line B){
	Point u=A.P-B.P;
	double t=Cross(B.v,u)/Cross(A.v,B.v);
	return A.P+A.v*t;
}
bool check(int cnt){
	sort(L+1,L+cnt+1);
	int head=1,tail=0; q[++tail]=L[1];
	for(int i=2;i<=cnt;++i){
		while(head<tail&&!On_Left(P[tail-1],L[i])) --tail;
		while(head<tail&&!On_Left(P[head],L[i])) ++head;
		q[++tail]=L[i];
		if(fabs(q[tail].ang-q[tail-1].ang)<eps){
			if(On_Left(L[i].P,q[--tail])) q[tail]=L[i];
		}
		if(head<tail) P[tail-1]=Line_Jiao(q[tail-1],q[tail]);
	}
	while(head<tail&&!On_Left(P[tail-1],q[head])) --tail;
	return tail-head>1;
}
void solve(int T){
	int cnt=0;
	for(int i=1;i<=n;++i)if(i!=T){
		if(v[T]<=v[i]&&u[T]<=u[i]&&w[T]<=w[i]){puts("No");return;}
		if(v[T]>=v[i]&&u[T]>=u[i]&&w[T]>=w[i])continue;
		double a=chty/v[i]+chty/w[T]-chty/v[T]-chty/w[i];
		double b=chty/u[i]+chty/w[T]-chty/u[T]-chty/w[i];
		double c=chty/w[i]-chty/w[T];
		if(fabs(a)>fabs(b)) L[++cnt]=Line(Point(-c/a,0),Point(b,-a));
		else L[++cnt]=Line(Point(0,-c/b),Point(b,-a));
	}
	L[++cnt]=Line(Point(0,0),Point(0,-1));
	L[++cnt]=Line(Point(0,0),Point(1,0));
	L[++cnt]=Line(Point(0,1),Point(-1,1));
	if(check(cnt)) puts("Yes");
	else puts("No");
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	while(scanf("%d",&n)!=EOF){
		for(int i=1;i<=n;++i)scanf("%lf%lf%lf",&v[i],&u[i],&w[i]);
		for(int i=1;i<=n;++i)solve(i);
	}
	return 0;
}

　　

　　

【LA4992】丛林警戒队

有一个很显然的结论：炸掉连续的点一定比炸掉分散的点更优，所有我们的做法就比较显然了

首先二分一个答案，然后判断半平面交是否为空即可

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
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 50010
#define eps 1e-6
#define INF 1e9
using namespace std;
struct Point{
	double x,y;
	Point(double a=0,double b=0):x(a),y(b){}
	inline void read(){scanf("%lf%lf",&x,&y);}
	inline void print(){printf("%.2lf %.2lf\n",x,y);}
	inline Point operator+(const Point &b){return Point(x+b.x,y+b.y);}
	inline Point operator-(const Point &b){return Point(x-b.x,y-b.y);}
	inline Point operator*(const double p){return Point(x*p,y*p);}
	inline Point operator/(const double p){return Point(x/p,y/p);}
	inline bool operator==(const Point &b)const{return fabs(x-b.x)<eps&&fabs(y-b.y)<eps;}
	inline bool operator< (const Point &b)const{return x<b.x||(x==b.x&&y<b.y);}
}A[MAXN],P[MAXN];
struct Line{
	Point P,v; double ang; Line(){}
	Line(Point A,Point B):P(A),v(B){ang=atan2(v.y,v.x);}
	inline bool operator< (const Line &b)const{return ang<b.ang;}
}L[MAXN],q[MAXN];
int n;
inline double Cross(Point A,Point B){return A.x*B.y-B.x*A.y;}
inline bool On_Left(Point A,Line L){return Cross(L.v,A-L.P)>0;}
inline Point Line_Jiao(Line A,Line B){
	Point u=A.P-B.P;
	double t=Cross(B.v,u)/Cross(A.v,B.v);
	return A.P+A.v*t;
}
bool check(int mid){
	for(int i=0;i<n;++i) L[i]=Line(A[i],A[i]-A[(i+mid+1)%n]);
	sort(L,L+n); int head=1,tail=0; q[++tail]=L[0];
	for(int i=1;i<n;++i){
		while(head<tail&&!On_Left(P[tail-1],L[i])) --tail;
		while(head<tail&&!On_Left(P[head],L[i])) ++head;
		q[++tail]=L[i];
		if(fabs(q[tail].ang-q[tail-1].ang)<eps){
			if(On_Left(L[i].P,q[--tail])) q[tail]=L[i];
		}
		if(head<tail) P[tail-1]=Line_Jiao(q[tail-1],q[tail]);
	}
	while(head<tail&&!On_Left(P[tail-1],q[head]))  --tail;
	return tail-head-1>0;
}
void solve(){
	for(int i=0;i<n;++i) A[i].read();
	int l=1,r=n;
	while(l+1<r){
		int mid=(l+r)>>1;
		if(check(mid)) l=mid;
		else r=mid;
	}
	printf("%d\n",check(l)?r:l);
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	while(scanf("%d",&n)!=EOF) solve();
	return 0;
}

　　

　　

　　

旋转卡壳

【LA4728】多边形

求完凸包之后，我们的问题就变成了一个经典问题：求凸包直径

直接上旋转卡壳即可

这题数据好水，怎么写都能过

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<bits/stdc++.h>
#define FILE "read"
#define MAXN 400100
#define eps 1e-6
#define INF 1e9
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
using namespace std;
struct Point{
	double x,y;
	Point(double a=0,double b=0):x(a),y(b){}
	inline Point operator+(const Point &b){return Point(x+b.x,y+b.y);}
	inline Point operator-(const Point &b){return Point(x-b.x,y-b.y);}
	inline Point operator*(const double p){return Point(x*p,y*p);}
	inline Point operator/(const double p){return Point(x/p,y/p);}
	inline bool operator==(const Point &b)const{return fabs(x-b.x)<eps&&fabs(y-b.y)<eps;}
	inline bool operator< (const Point &b)const{return x<b.x||(x==b.x&&y<b.y);}
}A[MAXN],q[MAXN];
int n;
inline int read(){
	int x=0,f=1;  char ch=getchar();
	while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
	while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
inline double Dot(Point A,Point B){return A.x*B.x+A.y*B.y;}
inline double Cross(Point A,Point B){return A.x*B.y-A.y*B.x;}
void solve(){
	n=read();  int cnt=0; double ans=0;
	for(int i=1;i<=n;++i){
		int x=read(),y=read(),w=read();
		A[++cnt]=Point(x,y);
		A[++cnt]=Point(x+w,y);
		A[++cnt]=Point(x,y+w);
		A[++cnt]=Point(x+w,y+w);
	}
	sort(A+1,A+cnt+1);  int tail=0;
	for(int i=1;i<=cnt;++i){
		while(tail>1&&Cross(q[tail]-q[tail-1],A[i]-q[tail-1])<=0) --tail;
		q[++tail]=A[i];
	}
	int lim=tail;
	for(int i=cnt-1;i;--i){
		while(tail>lim&&Cross(q[tail]-q[tail-1],A[i]-q[tail-1])<=0) --tail;
		q[++tail]=A[i];
	}
	int pos=2;  --tail;
	for(int i=1;i<=tail;++i){
		while(fabs(Cross(q[pos%tail+1]-q[i+1],q[i]-q[i+1]))>fabs(Cross(q[pos]-q[i+1],q[i]-q[i+1]))) pos%=tail,++pos;
		cmax(ans,Dot(q[pos]-q[i],q[pos]-q[i]));
	}
	printf("%.0lf\n",ans);
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	for(int T=read();T;--T) solve();
	return 0;
}

　　

　　

【bzoj1069】最大土地面积

按照计算几何的套路，求出凸包后，我们发现这四个点中一定包含了2个对踵点

于是上旋转卡壳求出一对对踵点后，在两侧找面积最大的三角形，然后拼在一起

找三角形时，只需要用叉积计算有向面积即可

时间复杂度：$O(n^2)$

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
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 2010
#define eps 1e-6
#define INF 1e9
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
using namespace std;
struct Point{
    double x,y;
    Point(double a=0,double b=0):x(a),y(b){}
    inline void read(){scanf("%lf%lf",&x,&y);}
    inline void print(){printf("%.2lf %.2lf\n",x,y);}
    inline Point operator+(const Point &b){return Point(x+b.x,y+b.y);}
    inline Point operator-(const Point &b){return Point(x-b.x,y-b.y);}
    inline Point operator*(const double p){return Point(x*p,y*p);}
    inline Point operator/(const double p){return Point(x/p,y/p);}
    inline bool operator==(const Point &b)const{return fabs(x-b.x)<eps&&fabs(y-b.y)<eps;}
    inline bool operator< (const Point &b)const{return x<b.x||(x==b.x&&y<b.y);}
}A[MAXN],q[MAXN];
int n,tail;
double ans;
inline double Cross(Point A,Point B){return A.x*B.y-A.y*B.x;}
void solve(Point A,Point B){
    double minn=0,maxx=0;
    for(int i=1;i<=tail;++i){
        cmax(maxx,Cross(A-q[i],B-q[i])/2);
        cmin(minn,Cross(A-q[i],B-q[i])/2);
    }
    cmax(ans,maxx-minn);
}
int main(){
    freopen(FILE".in","r",stdin);
    freopen(FILE".out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;++i) A[i].read();
    sort(A+1,A+n+1);
    for(int i=1;i<=n;++i){
        while(tail>1&&Cross(q[tail]-q[tail-1],A[i]-q[tail-1])<=0) --tail;
        q[++tail]=A[i];
    }
    int lim=tail;
    for(int i=n-1;i;--i){
        while(tail>lim&&Cross(q[tail]-q[tail-1],A[i]-q[tail-1])<=0) --tail;
        q[++tail]=A[i];
    }
    int pos=2; --tail;
    for(int i=1;i<=tail;++i){
        while(fabs(Cross(q[pos%tail+1]-q[i+1],q[i]-q[i+1]))>fabs(Cross(q[pos]-q[i+1],q[i]-q[i+1]))) pos%=tail,++pos;
        solve(q[i],q[pos]);
    }
    printf("%.3lf\n",ans);
    return 0;
}

　　

　　

【UVa12307】最小包围盒

旋转卡壳经典应用：求最小矩形覆盖

首先有一个结论：该矩形一定有一条边与凸包的一条边重合（想想旋转卡壳的原理就知道了）

那么我们的做法就是找到对踵点后，补全这个矩形，然后更新答案

找矩形左右极点时用点积判断，具体参见代码

然后注意：INF不要开小

这题最坑的地方就是卡精度：我的程序eps开到1e-10才过

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<bits/stdc++.h>
#define FILE "read"
#define MAXN 100100
#define eps 1e-10
#define INF 1e15
#define cmin(a,b) a=min(a,b)
#define cmax(a,b) a=max(a,b)
using namespace std;
struct Point{
	double x,y;
	Point(double a=0,double b=0):x(a),y(b){}
	inline void read(){scanf("%lf%lf",&x,&y);}
	inline void print(){printf("%.2lf %.2lf\n",x,y);}
	inline Point operator+(const Point &b){return Point(x+b.x,y+b.y);}
	inline Point operator-(const Point &b){return Point(x-b.x,y-b.y);}
	inline Point operator*(const double p){return Point(x*p,y*p);}
	inline Point operator/(const double p){return Point(x/p,y/p);}
	inline bool operator==(const Point &b)const{return fabs(x-b.x)<eps&&fabs(y-b.y)<eps;}
	inline bool operator< (const Point &b)const{return x<b.x||(x==b.x&&y<b.y);}
}A[MAXN],q[MAXN];
int n;
inline int dcmp(double x){
	if(fabs(x)<eps) return 0;
	else return x<0?-1:1;
}
inline double Dot(Point A,Point B){return A.x*B.x+A.y*B.y;}
inline double Cross(Point A,Point B){return A.x*B.y-A.y*B.x;}
inline double Lenth(Point A){return sqrt(Dot(A,A));}
void solve(){
	for(int i=1;i<=n;++i) A[i].read();
	sort(A+1,A+n+1);  int tail=0;
	for(int i=1;i<=n;++i){
		while(tail>1&&Cross(q[tail]-q[tail-1],A[i]-q[tail-1])<=0) --tail;
		q[++tail]=A[i];
	}
	int lim=tail;
	for(int i=n-1;i;--i){
		while(tail>lim&&Cross(q[tail]-q[tail-1],A[i]-q[tail-1])<=0) --tail;
		q[++tail]=A[i];
	}
	int pos=2; --tail;
	int l=0,r=1;  double ans1=INF,ans2=INF;
	for(int i=1;i<=tail;++i){
		while(fabs(Cross(q[pos%tail+1]-q[i],q[i+1]-q[i]))>fabs(Cross(q[pos]-q[i],q[i+1]-q[i]))) pos%=tail,++pos;
		if(!l) l=pos;
		while(dcmp(Dot(q[i+1]-q[i],q[r%tail+1]-q[r]))>0) r%=tail,++r;
		while(dcmp(Dot(q[i+1]-q[i],q[l%tail+1]-q[l]))<0) l%=tail,++l;
		double h=Cross(q[i+1]-q[i],q[pos]-q[i])/Lenth(q[i+1]-q[i]);
		double w=(Dot(q[i+1]-q[i],q[r]-q[i])-Dot(q[i+1]-q[i],q[l]-q[i]))/Lenth(q[i+1]-q[i]);
		cmin(ans1,w*h);  cmin(ans2,(w+h)*2);  
	}
	printf("%.2lf %.2lf\n",ans1,ans2);
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	while(scanf("%d",&n)!=EOF&&n) solve();
	return 0;
}

本文标题:【算法笔记】计算几何题目总结

文章作者:chty

发布时间:2017年05月24日 - 21时47分

最后更新:2018年07月09日 - 20时18分

许可协议:本文为博主原创，未经许可不得转载。

文章目录
  1. 1. 入门题目
    1. 1.1. 【UVa11178】Morley定理
    2. 1.2. 【CF772#B】不稳定的风筝
    3. 1.3. 【LA3263】好看的一笔画
    4. 1.4. 【UVa11796】狗的距离
  2. 2. 凸包
    1. 2.1. 【UVa10652】包装木板
    2. 2.2. 【LA2453】围墙
    3. 2.3. 【UVa11168】飞机场
    4. 2.4. 【UVa10256】点集划分
  3. 3. 半平面交
    1. 3.1. 【POJ3130】数学家的难题
    2. 3.2. 【LA2512】艺术画廊
    3. 3.3. 【UVa10084】更冷更热
    4. 3.4. 【LA3890】离海最远的点
    5. 3.5. 【LA2218】铁人三项
    6. 3.6. 【LA4992】丛林警戒队
  4. 4. 旋转卡壳
    1. 4.1. 【LA4728】多边形
    2. 4.2. 【bzoj1069】最大土地面积
    3. 4.3. 【UVa12307】最小包围盒
,