平面几何

1
2
3
4
5
struct Point{
double x,y;
Point(){}
Point(double _,double __){x=_,y=__;}
};

线

1
2
3
4
5
6
struct Line{//使用向量式表示,线上的点X满足X=P+tV,直线t∈R,线段t∈[0,1],射线t>0
Point P;//线上一点
Vector V;//方向向量,已知线上两个不同点A、B,则V=B-A
Line(){}
Line(Point _,Vector __){P=_,V=__;}
};

1
2
3
4
5
6
7
8
9
struct Circle{
Point c;
double r;
Circle(){}
Circle(Point _,double __){c=_,r=__;}
Point point(double a){////通过圆心角确定圆上坐标
return Point(c.x+cos(a)*r,c.y+sin(a)*r);
}
};

多边形

1
2
3
4
struct Polygon{
int n;
vector<Point> P;
};

向量

1
typedef Point Vector;

四则运算

1
2
3
4
Vector operator + (Vector A,Vector B){return Vector(A.x+B.x,A.y+B.y);}
Vector operator - (Vector A,Vector B){return Vector(A.x-B.x,A.y-B.y);}
Vector operator * (Vector A,double p){return Vector(A.x*p,A.y*p);}
Vector operator / (Vector A,double p){return Vector(A.x/p,A.y/p);}

点积与叉积

点积几何意义:$U$在$V$上的投影的模长乘$V$的模长,可以判断向量垂直

叉积几何意义:以$U$、$V$为邻边构成的平行四边形的有向面积,可以判断向量平行

把点积和叉积组合到一起可以判断两个向量的位置关系

左图点积,右图叉积:对于向量$a$、$b$,$b$在蓝色区域为正,绿色区域为负

1
2
double Dot(Vector A,Vector B){return A.x*B.x+A.y*B.y;}//|A||B|cos(θ)
double Cross(Vector A,Vector B){return A.x*B.y-A.y*B.x;}//|A||B|sin(θ)

模长、投影与夹角

1
2
3
double Length(Vector A){return sqrt(Dot(A,A));}
double Shade(Vector A,Vector B){return Dot(A,B)/Length(B);}
double Angle(Vector A,Vector B){return acos(Dot(A,B)/Length(A)/Length(B));}

极角

1
double Polar(Vector A){return atan2(A.y,A.x);}

旋转与单位法向量

1
2
3
4
5
Vector Rotate(Vector A,double rad){return Vector(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));}
Vector Normal(Vector A){//左转90°,长度归1
double L=Length(A);
return Vector(-A.y/L,A.x/L);
}

距离

两点间距离

1
double DistanceToPoint(Point A,Point B){return Length(A-B);}

点到直线间距离

1
double DistanceToLine(Line A,Point B){return fabs(Cross(B-A.P,A.V)/Length(A.V));}

点到线段间距离

1
2
3
4
5
6
7
8
//点到线段的距离
double DistanceToSegment(Point P,Point A,Point B){
if(A==B) return Length(P-A);
Vector v1=B-A,v2=P-A,v3=P-B;
if(dcmp(Dot(v1,v2))<0) return Length(v2);
if(dcmp(Dot(v1,v3))>0) return Length(v3);
return fabs(Cross(v1,v2))/Length(v1);
}

关系

两直线交点

1
2
3
4
5
//须确保两直线有唯一交点
Point GetLineIntersection(Line A,Line B){
double t=Cross(B.V,A.P-B.P)/Cross(A.V,B.V);
return A.P+A.V*t;
}

点在多边形内判定

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int isPointInPolygon(Point p,Polygon poly){//转角法
int wn=0;
int n=poly.size();
for(int i=0;i<n;i++){
Point C=poly[i],D=poly[(i+1)%n];
if(OnSegment(p,C,D) return -1;//在边界上
int k=dcmp(Cross(D-C,p-C));
int d1=dcmp(C.y-p.y),d2=dcmp(D.y-p.y);
if(k>0&&d1<=0&&d2>0) wn++;
if(k<0&&d2<=0&&d1>0) wn++;
}
if(wn!=0) return 1;//内部
return 0;//外部
}

线段相交判定

1
2
3
4
5
6
//线段规范相交判定,即交点不在任何一条线段的端点
bool SegmentProperIntersection(Point a1,Point a2,Point b1,Point b2){
double c1=Cross(a2-a1,b1-a1),c2=Cross(a2-a1,b2-a1);
double c3=Cross(b2-b1,a1-b1),c4=Cross(b2-b1,a2-b1);
return dcmp(c1)*dcmp(c2)<0&&dcmp(c3)*dcmp(c4)<0;
}

点在线段上判定

1
2
3
4
//判断点是否在线段上,不包含端点
bool OnSegment(Point P,Point A,Point B){
return dcmp(Cross(A-P,B-P)==0&&dcmp(Dot(A-P,B-P))<0;
}

直线与圆的交点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//联立方程组
//直线和圆的交点,返回交点个数,结果存在sol中。
//该代码没有清空sol
int getLineCircleIntersecion(Line L,Circle C,double &t1,double &t2,vector<Point> &sol){
double a=L.v.x,b=L.p.x-C.c.x,c=L.v.y,d=L.p.y-C.c.y;
double e=a*a+c*c,f=2*(a*b+c*d),g=b*b+d*d-C.r*C.r;
double delta=f*f-4*e*g; //判别式
if(dcmp(delta)<0) return 0; //相离
if(dcmp(delta)==0){ //相切
t1=t2=-f/(2*e);
sol.push_back(C.point(t1));
return 1;
}
//相交
t1=(-f-sqrt(delta))/(2*e);sol.push_back(C.point(t1));
t2=(-f+sqrt(delta))/(2*e);sol.push_back(C.point(t2));
return 2;
}

两圆相交

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int getCircleCircleIntersection(Circle C1,Circle C2,vector<Point> &sol){
double d=Length(C1.c-C2.c);
if(dcmp(d)==0){
if(dcmp(C1.r-C2.r==0)) return -1;//两圆完全重合
return 0;//两圆为同心圆
}
if(dcmp(C1.r+C2.r-d)<0) return 0;
if(dcmp(fabs(C1.r-C2.r)==0)) return -1;
double a=Angle(C2.c-C1.c);//向量C1C2的极角
double da=acos((C1.r*C1.r+d*d-C2.r*C2.r)/(2*C1.r*d));
//C1C2到C1P1的角
Point p1=C1.point(a-da),p2=C1.point(a+da);
sol.push_back(p1);
if(p1==p2) return 1;
sol.push_back(p2);
return 2;
}

过定点做圆的切线

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int getTangents(Point p,Circle C,Vector *v){
Vector u=C.c-p;
double dist=Length(u);
if(dist<C.r) return 0;
else if(dcmp(dist-C.r)==0){
v[0]=Rotate(u,PI/2);
return 1;
}
else{
double ang=asin(C.r/dist);
v[0]=Rotate(u,-ang);
v[1]=Rotate(u,+ang);
return 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
//根据圆心距判断
//返回切线的个数,-1表示有无数条公切线。
//a[i], b[i] 表示第i条切线在圆A,圆B上的切点
int getTangents(Circle A,Circle B,Point *a,Point *b){
int cnt=0;
if(A.r<B.r){swap(A,B);swap(a,b);}
int d2=(A.c.x-B.c.x)*(A.c.x-B.c.x)+(A.c.y-B.c.y)*(A.c.y-B.c.y);
int rdiff=A.r-B.r;
int rsum=A.r+B.r;
if(d2<rdiff*rdiff) return 0;//内含
double base=atan2(B.c.y-A.c.y,B.c.x-A.c.x);
if(d2==0&&A.r==B.r) return -1;//无限多条切线
if(d2==rdiff*rdiff){//内切,一条切线
a[cnt]=A.point(base),b[cnt]=B.point(base),cnt++;
return 1;
}
//有外共切线
double ang=acos((A.r-B.r)/sqrt(d2));
a[cnt]=A.point(base+ang);b[cnt]=B.point(base+ang);cnt++;
a[cnt]=A.point(base-ang);b[cnt]=B.point(base-ang);cnt++;
if(d2==rsum*rsum){//一条内公切线
a[cnt]=A.point(base);
b[cnt]=B.point(PI+base);
cnt++;
}
else if(d2>rsum*rsum){//两条内公切线
double ang=acos((A.r+B.r)/sqrt(d2));
a[cnt]=A.point(base+ang);b[cnt]=B.point(PI+base+ang);cnt++;
a[cnt]=A.point(base-ang);b[cnt]=B.point(PI+base-ang);cnt++;
}
return cnt;
}

面积

多边形的有向面积

1
2
3
4
5
6
double PolygonArea(Polygon A){
double area=0;
for(int i=1;i<A.size()-1;i++)
area+=Cross(A[i].P-A[0].P,A[i+1].P-A[0].P);
return area/2;
}

凸包

包围给定点集的面积最小的凸多边形

Andrew算法

分别维护上下凸壳,然后合并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void ConvexHull(Point *p,int n,Point* ch){
sort(p,p+n,cmp);//按照x、y为第一、二关键字排序
int m=0;
for(int i=0;i<n;i++){
while(m>1&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;//右手定则,直到方向在左边为止
ch[m++]=p[i];
}
int k=m;
for(int i=n-2;i>=0;i--){
while(m>k&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
ch[m++]=p[i];
}
if(n>1) m--;
}

半平面交

给出若干个半平面,求它们的公共部分

半平面

半平面用有向直线表示,它的左侧就是它所代表的半平面

增量法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void InitPolygon(Polygon &poly)//初始化答案为整个平面,结束后删除
{
poly[poly.n++]=Point(INF,INF);
poly[poly.n++]=Point(INF,-INF);
poly[poly.n++]=Point(-INF,INF);
poly[poly.n++]=Point(-INF,-INF);
}

Polygon CutPolygon(Polygon poly,Point A,Point B){
Polygon newpoly;
int n=poly.size();
for(int i=0;i<n;i++){
Point C=poly[i],D=poly[(i+1)%n];//逆时针考虑多边形的所有顶点
if(dcmp(Cross(B-A,C-A))>=0) newpoly.push_back(C);
if(dcmp(Cross(B-A,C-D))!=0){
Point ip=GetLineIntersection(A,B-A,C,D-C);
if(OnSegment(ip,C,D)) newpoly.push_back(ip);
}
}
return newpoly;
}

旋转卡壳

凸包上被两条平行直线卡住的点对互为对踵点,对踵点对的数量是$O(n)$的

旋转卡壳目的是求出凸包上所有的对踵点对

给定 $n$ 个点,最远点对一定是凸包上的对踵点对

1
2


随机增量法

最小圆覆盖

Voronoi图与Delaunay三角剖分

公式与性质

Pick公式

在格点图上,整点多边形的面积=内部整点个数+边上的整点个数/2−1

欧拉公式

简单多面体的顶点数V,面数F与棱数E之间存在如下关系

特别的,在平面图上:点数V,将平面分成的互不联通的区域数F,边数E与联通块个数W之间,有

三角形的心

  • 外心:外接圆圆心,三条中垂线交点
  • 内心:内接圆圆心,三条角平分线交点
  • 重心:三条中线交点,注意其物理性质
  • 垂心:三条垂线交点
  • 旁心:一个外交平分线与另外两个内角平分线交点

平面多边形的重心:所以顶点x/y坐标的平均数

分享到: