计算几何点线面形基础知识总结模板：
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<cstdlib> using namespace std; const double eps=1e-8; const double inf=1e20;int sgn(double x){ if(abs(x)<eps) return 0; if(x<0) return -1; return 1; } struct Point{ double x,y; Point(double xx=0,double yy=0):x(xx),y(yy){} bool operator == (const Point& b)const{ sgn(x-b.x)==0&&sgn(y-b.y)==0; } Point operator + (const Point& b)const{ return Point(x+b.x,y+b.y); } Point operator - (const Point& b)const{ return Point(x-b.x,y-b.y); } Point operator * (const double& k)const{ //返回相乘后的点 return Point(x*k,y*k); } Point operator / (const double& k)const{ //返回相除后的点 return Point(x/k,y/k); } double operator * (const Point& b)const{ //点乘 return x*b.x+y*b.y; } double operator ^ (const Point& b)const{ //叉乘 return x*b.y-b.x*y; } double len(){ //返回长度 return sqrt(x*x+y*y); } double len2(){ //返回长度的平方 return x*x+y*y; } Point norm(double r){ //标准化，返回将长度化为r的点 double l=len(); if(!sgn(l)) return *this; r/=l; return Point(x*r,y*r); } //绕原点旋转角度b（弧度值），后x、y的变化 void transXY(double b){ double tx=x,ty=y; x=tx*cos(b)-ty*sin(b); y=tx*sin(b)+ty*cos(b); } }; struct Line{ Point s,e; Line(){} Line(Point ss,Point ee){ s=ss,e=ee; } //返回点p在直线上的投影 Point PointProg(Point p){ return s+(((e-s)*((e-s)*(p-s)))/((e-s).len2())); } //返回点p关于直线的对称点 Point PointSymmetry(Point p){ Point q=PointProg(p); return Point(2*q.x-p.x,2*q.y-p.y); } //点是否在直线上 bool PointOnLine(Point p){ return sgn((p-s)^(e-s))==0; } //点是否在线段上 bool PointOnSeg(Point p){ return sgn((p-s)^(e-s))==0&&sgn((p-s)*(p-e))<=0; } //两直线相交求交点 //第一个值为0表示直线重合，为1表示平行，为2表示相交 //只有第一个值为2时，交点才有意义 pair<int,Point> operator &(const Line &b)const{ Point res = s; if(sgn((s-e)^(b.s-b.e)) == 0) { if(sgn((s-b.e)^(b.s-b.e)) == 0) return make_pair(0,res);//重合 else return make_pair(1,res);//平行 } double t = ((s-b.s)^(b.s-b.e))/((s-e)^(b.s-b.e)); res.x += (e.x-s.x)*t; res.y += (e.y-s.y)*t; return make_pair(2,res); } }; struct Circle{ Point p; double r; Circle(){} Circle(Point pp,double rr){ p=pp,r=rr; } //求直线与圆的交点，返回交点个数 int LineCrossCircle1(Line l,Point &p1,Point &p2){ double dx=l.e.x-l.s.x,dy=l.e.y-l.s.y; double a=dx*dx+dy*dy; double b=2*dx*(l.s.x-p.x)+2*dy*(l.s.y-p.y); double c=(l.s.x-p.x)*(l.s.x-p.x)+(l.s.y-p.y)*(l.s.y-p.y)-r*r; double d=b*b-4*a*c; if(sgn(d)<0) return 0; int res=0; double ans1=(-b-sqrt(d))/(2.0*a); double ans2=(-b+sqrt(d))/(2.0*a); p1=Point(l.s.x+ans1*dx,l.s.y+ans1*dy); ++res; p2=Point(l.s.x+ans2*dx,l.s.y+ans2*dy); ++res; if(res==2&&sgn(ans1-ans2)==0) --res; return res; } //求射线与圆的交点，返回交点个数 int LineCrossCircle2(Line l,Point &p1,Point &p2){ double dx=l.e.x-l.s.x,dy=l.e.y-l.s.y; double a=dx*dx+dy*dy; double b=2*dx*(l.s.x-p.x)+2*dy*(l.s.y-p.y); double c=(l.s.x-p.x)*(l.s.x-p.x)+(l.s.y-p.y)*(l.s.y-p.y)-r*r; double d=b*b-4*a*c; if(sgn(d)<0) return 0; int res=0; double ans1=(-b-sqrt(d))/(2.0*a); double ans2=(-b+sqrt(d))/(2.0*a); if(sgn(ans1)>=0){ p1=Point(l.s.x+ans1*dx,l.s.y+ans1*dy); ++res; } if(sgn(ans2)>=0){ p2=Point(l.s.x+ans2*dx,l.s.y+ans2*dy); ++res; } if(res==2&&sgn(ans1-ans2)==0) --res; return res; } }; //判断线段相交 bool inter(Line l1,Line l2){ return max(l1.s.x,l1.e.x)>=min(l2.s.x,l2.e.x)&& max(l2.s.x,l2.e.x)>=min(l1.s.x,l1.e.x)&& max(l1.s.y,l1.e.y)>=min(l2.s.y,l2.e.y)&& max(l2.s.y,l2.e.y)>=min(l1.s.y,l1.e.y)&& sgn((l1.s-l2.s)^(l2.e-l2.s))*sgn((l1.e-l2.s)^(l2.e-l2.s))<=0&& sgn((l2.s-l1.s)^(l1.e-l1.s))*sgn((l2.e-l1.s)^(l1.e-l1.s))<=0; } double dis(Point a,Point b){ return sqrt((b-a)*(b-a)); } //判断点在线段上 bool OnSeg(Point P,Line L){ return sgn((L.s-P)^(L.e-P))==0&& sgn((P.x-L.s.x)*(P.x-L.e.x))<=0&& sgn((P.y-L.s.y)*(P.y-L.e.y))<=0; } //判断点在凸多边形内，复杂度O(n) //点形成一个凸包，而且按逆时针排序（如果是顺时针把里面的<0改为>0） //点的编号:0~n-1 //返回值： //-1:点在凸多边形外 //0:点在凸多边形边界上 //1:点在凸多边形内 int inConvexPoly(Point a,Point p[],int n){ for(int i=0;i<n;++i) if(sgn((p[i]-a)^(p[(i+1)%n]-a))<0) return -1; else if(OnSeg(a,Line(p[i],p[(i+1)%n]))) return 0; return 1; } //判断点在任意多边形内,复杂度O(n) //射线法，poly[]的顶点数要大于等于3,点的编号0~n-1，按逆时针或顺时针排序 //返回值 //-1:点在凸多边形外 //0:点在凸多边形边界上 //1:点在凸多边形内 int inPoly(Point a,Point p[],int n){ int cnt=0; Line ray,side; ray.s=a; ray.e.y=a.y; ray.e.x=-inf; for(int i=0;i<n;++i){ side.s=p[i]; side.e=p[(i+1)%n]; if(OnSeg(a,side)) return 0; if(sgn(side.s.y-side.e.y)==0) continue; if(OnSeg(side.s,ray)){ if(sgn(side.s.y-side.e.y)>0) ++cnt; } else if(OnSeg(side.e,ray)){ if(sgn(side.e.y-side.s.y)>0) ++cnt; } else if(inter(ray,side)) ++cnt; } if(cnt%2==1) return 1; else return -1; } //判断凸多边形 //允许共线边 //点可以是顺时针给出也可以是逆时针给出 //点的编号是0～n-1 bool isconvex(Point poly[],int n){ bool s[3]; memset(s,false,sizeof(s)); for(int i=0;i<n;++i){ s[sgn((poly[(i+1)%n]-poly[i])^(poly[(i+2)%n]-poly[i]))+1]=true; if(s[0]&&s[2]) return false; } return true; } //点到线段的距离 //返回点到线段最近的点 Point NearestPointToLineSeg(Point P,Line L){ Point result; double t=((P-L.s)*(L.e-L.s))/((L.e-L.s)*(L.e-L.s)); if(t>=0&&t<=1){ result.x=L.s.x+(L.e.x-L.s.x)*t; result.y=L.s.y+(L.e.y-L.s.y)*t; } else{ if(dis(P,L.s)<dis(P,L.e)) return L.s; else return L.e; } return result; }
以pt点为中心进行极角排序：
struct Point{ int id,x,y; Point(){} Point(int x,int y):x(x),y(y){} }p1[maxn],p2[maxn],pt; Point operator - (const Point& a,const Point& b){ return Point(a.x-b.x,a.y-b.y); } bool operator ^ (const Point& a,const Point& b){ return (1LL*a.x*b.y-1LL*b.x*a.y)>0; } //返回向限 inline int Quadrant(const Point& a){ if(a.x>0&&a.y>=0) return 1; else if(a.x<=0&&a.y>0) return 2; else if(a.y<=0&&a.x<0) return 3; else if(a.x>=0&&a.y<0) return 4; } //以pt为中心进行极角排序 bool operator < (const Point& c,const Point& d){ Point a=c-pt,b=d-pt; int qa=Quadrant(a),qb=Quadrant(b); if(qa!=qb) return qa<qb; return a^b; }
（其中叉积求直线的交点的证明见https://www.cnblogs.com/jklover/p/10484313.html，叉积判断线段相交用到了快速排斥实验和跨立实验。）
判断线段是否在多边形内：当多边形为凸时，只需判断线段的两个端点在多边形内即可。
当多边形为凹时，其伪代码如下，复杂度为O(n)：
