基础
-
点（向量）：看作 的矩阵，点积意为投影，叉积意为面积，正负按右手定则。
-
点排序：按 pair 排；线排序：按极角 排，平行则上面排前面。
bool operator <(Line &a) { double x=angle(),y=a.angle(); if(abs(x-y)<eps) return (v^(a.P-P))<0; return x<y; } -
两线交点：平行则不交，端点出发按比例移动到交点，比例按叉积算面积比例来算。
Point inter(const Line &a,const Line &b) { if(abs(a.v^b.v)<eps) return {7-p,p+9}; //not_inter return a.P+a.v*(((b.P-a.P)^b.v)/(a.v^b.v)); } -
两线夹角：点积定义即可：
-
点/向量顺时针旋转：
-
点到直线的距离：叉积算面积除以底；点到线段的距离：特判点，点积看是否在两端点外，规约到直线。
double point_to_seg(const Point &x,const Point &a,const Point &b) { if(a==b) return (x-a).mo(); Vector v1=b-a,v2=x-a,v3=x-b; if(v1*v2<0) return v2.mo(); if(v1*v3>0) return v3.mo(); return point_to_line(x, a, b); } -
点在直线上：与两端点连线叉积为 ；点在线段上：且内向连线点积 .
凸包
-
求凸包：将点排序，依次往里加点同时维护凸性即可，正反做一遍，凸性用叉积判即可，平的就看是否新的更短即可，得到凸包逆时针序点集。
bool tu(const Point &a,const Point &b,const Point &c) { double pos=(a-c)^(b-c); if(abs(pos)>eps) return pos<0; return (a-c).mo()<(b-c).mo()+eps; } int n;Point P[N],h[N<<1];int tail; void hull() { sort(P+1,P+n+1); h[++tail]=P[1],h[++tail]=P[2]; for(rint i=3;i<=n;h[++tail]=P[i],i++) while(tail>1&&!tu(P[i],h[tail],h[tail-1])) tail--; h[++tail]=P[n-1]; for(rint i=n-2;i;h[++tail]=P[i],i--) while(tail>1&&!tu(P[i],h[tail],h[tail-1])) tail--; //h[tail]==h[1] } -
旋转卡壳：求凸包直径，发现具有单调性和单峰性，枚举边同时单指针跟着走即可，用叉积判距离即可。
double hull_len() { if(tail<=3) return (h[1]-h[tail-1]).mo(); double ans=0; for(rint i=1,j=3;i<tail;i++) { while(((h[i+1]-h[i])^(h[j]-h[i]))<((h[i+1]-h[i])^(h[j+1]-h[i]))) j=(j==tail-1?1:j+1); ans=max(ans,max((h[j]-h[i]).mo(),(h[j]-h[i+1]).mo())); } return ans; } -
闵可夫斯基和：求两凸包点集之和形成的凸包，容易发现新凸包的边由原两凸包边组成，找到左下点然后一步步贪心加边即可。
int n,m,q,num1,num2; Point h1[N<<1],h2[N<<1],H[N<<2];int cnt; void minkfusji() { H[cnt=1]=h1[1]+h2[1]; int now1=1,now2=1; while(now1<num1&&now2<num2) { if(((h1[now1+1]-h1[now1])^(h2[now2+1]-h2[now2]))>0) H[cnt+1]=H[cnt]+h1[now1+1]-h1[now1],now1++,cnt++; else H[cnt+1]=H[cnt]+h2[now2+1]-h2[now2],now2++,cnt++; } while(now1<num1) H[cnt+1]=H[cnt]+h1[now1+1]-h1[now1],now1++,cnt++; while(now2<num2) H[cnt+1]=H[cnt]+h2[now2+1]-h2[now2],now2++,cnt++; } -
动态凸包：增量法，set 维护上下凸壳点集，势能分析复杂度是 ，二分找推平的区间端点即可。
-
三维凸包：考虑 增量法，每次加点暴力枚举所有面看有没有被看到即可，要扰动点避免四点共面。
mt19937 rd(time(0)); struct Point{ double x,y,z; Point operator-(const Point &a)const{return {x-a.x,y-a.y,z-a.z};} double operator*(const Point &a)const{return x*a.x+y*a.y+z*a.z;} Point operator^(const Point &a)const{return {y*a.z-z*a.y,z*a.x-x*a.z,x*a.y-y*a.x};} double mo(){return sqrt(x*x+y*y+z*z);} void shake(){x+=rd(),y+=rd(),z+=rd();} }P[N]; struct Plane{ int e[3]; Vector fa(){return (P[e[1]]-P[e[0]])^(P[e[2]]-P[e[0]]);} double area(){return fa().mo()/2;} bool above(const Point &a){return (a-P[e[0]])*fa()>=0;} }pl[N<<1],res[N<<1]; int n,m; bool use[N][N]; void hull() { pl[++m]={1,2,3},pl[++m]={3,2,1}; for(rint i=4;i<=n;i++) { int cnt=0; for(rint j=1;j<=m;j++) { bool in=pl[j].above(P[i]); if(!in) res[++cnt]=pl[j]; for(rint k=0;k<3;k++) use[pl[j].e[k]][pl[j].e[(k+1)%3]]=in; } for(rint j=1;j<=m;j++) for(rint k=0;k<3;k++) { int x=pl[j].e[k],y=pl[j].e[(k+1)%3]; if(use[x][y]&&!use[y][x]) res[++cnt]={x,y,i}; } m=cnt; for(rint j=1;j<=m;j++) pl[j]=res[j]; } } double hull_area() { hull(); double ans=0; for(rint i=1;i<=m;i++) ans+=pl[i].area(); return ans; }
半平面交
-
求半平面交：将线排序，维护有效线的双端队列，依次往里加线，对于尾首维护交点在右，加完了再将尾首对起来维护，得到左半平面交，凸包点即为相邻两线交点，不封闭可以在外面框一层边界。
Line line[N];int n; int q[N],hh=1,tt; Point cut[N];int num; bool isright(const Line &a,const Line &b,const Line &c) { Point P=inter(b,c); return (a.v^(P-a.P))<-eps; } void halfcut() { sort(line+1,line+n+1); for(rint i=1;i<=n;i++) { while(hh<tt&&isright(line[i],line[q[tt]],line[q[tt-1]])) tt--; while(hh<tt&&isright(line[i],line[q[hh]],line[q[hh+1]])) hh++; q[++tt]=i; } while(hh<tt&&isright(line[q[hh]],line[q[tt]],line[q[tt-1]])) tt--; while(hh<tt&&isright(line[q[tt]],line[q[hh]],line[q[hh+1]])) hh++; q[++tt]=q[hh]; for(rint i=hh;i<tt;i++) cut[++num]=inter(line[q[i]],line[q[i+1]]); }
圆
-
三点定圆：即求外心，求两角平分线交点即可。
Circle get_circle(const Point &a,const Point &b,const Point &c) { Line ab={(a+b)*0.5,rotate(b-a,Pi/2)}, bc={(b+c)*0.5,rotate(c-b,Pi/2)}; Point P=inter(ab,bc); return {P,dis(P,a)}; } -
最小圆覆盖：随机增量法，每次加入的点若不在圆内则新圆必过该点，循环三层即可，将点集打乱后每次暴力重来复杂度是 .
int n;Point P[N]; Circle min_circle() { mt19937 rd(time(0)); shuffle(P+1,P+n+1,rd); Circle c={P[1],0}; for(rint i=2;i<=n;i++) if(dis(c.P,P[i])-c.r>eps) { c={P[i],0}; for(rint j=1;j<i;j++) if(dis(c.P,P[j])-c.r>eps) { c={(P[i]+P[j])*0.5,dis(P[i],P[j])/2}; for(rint k=1;k<j;k++) if(dis(c.P,P[k])-c.r>eps) c=get_circle(P[i],P[j],P[k]); } } return c; } -
圆反演：
- 圆内外的点一一映射， 与 互为反演关系 且 共线。
- 不过反演圆心的圆反演后仍为圆，，过反演圆心的点反演后为两交点连成的直线。
- 两图形相切其对应的反演图形也相切。
- 应用：求过两圆外一点且与两圆相切的所有的圆。考虑以该点为反演圆心做圆反演，半径任意，那么符合条件的圆的反演为与两圆反演后的两圆的公切线，动手做点辅助线就可以推出来了。
复杂图形面积并
- 辛普森积分法：大致对于图形划分边界，对于每个边界内部用辛普森积分法计算，不断往下递归直到左半右半估算之和与总体估算误差很小，估算公式为 ，可以要求递归层数。
double f(double x)
{
//暴力计算横坐标x被覆盖的长度和
}
double cal(double l,double r)
{
return (r-l)*(f(l)+4*f((r+l)/2)+f(r))/6;
}
double sim(double l,double r,double ans,double Eps=eps,int dep=1)
{
double mid=(l+r)/2,lans=cal(l,mid),rans=cal(mid,r);
if(abs(lans+rans-ans)<=15*Eps&&dep<0) return lans+rans+(lans+rans-ans)/15;
return sim(l,mid,lans,Eps/2,dep-1)+sim(mid,r,rans,Eps/2,dep-1);
}
double work()
{
double ans=0;
for(rint i=1;i<n;i++) ans+=sim(step[i],step[i+1],cal(step[i],step[i+1]));
return ans;
}
三角剖分
- 凸包：随便选一个点作为中心，把所有边作为底与该点连边就可以了。
- 任意多边形：若可以负面积则按凸包的做就可以了，否则 每次暴力找一个凸角剖分递归下去，不会更优复杂度的做法。
