计算几何的特点：
基本定义：
1.向量：参考初中数学教材。
意义：计算几何的单位不是点而是向量。
2.点积：$a\cdot b=|a||b|cos<a,b>=a.x*b.x+a.y*b.y$。
意义：若$a\cdot b=0$则两向量垂直，若$a\cdot b<0$则两向量夹角$>\frac{\pi}{2}$，若$a\cdot b>0$则两向量夹角$<\frac{\pi}{2}$。
3.叉积：$a\times b=|a||b|sin<a,b>=a.x*b.y-a.y*b.x$。
意义：若$a\times b=0$则两向量共线，若$a\times b>0$则b在a的逆时针方向，若$a\times b<0$则b在a的顺时针方向。
基础操作：
1.向量旋转：$(rcosA,rsinA)\rightarrow (rcos(A+B),rsin(A+B))$
有$(rcos(A+B),rsin(A+B))=(rcosAcosB-rsinAsinB,rsinAcosB+rcosAsinB)$
将坐标带入得到$(x,y)\rightarrow (xcosB-ysinB,ycosB+xsinB)$。
2.极角排序：将所有点按顺时针/逆时针排序。（有些时候要分象限讨论）
方法一：对于点$(x,y)$使用$atan2(y,x)$即可求出极角（弧度制），但精度堪忧。
方法二：使用叉积判断，较为常用。
3.两直线夹角：求直线$a,b$相交形成的角度$\theta$。
由于$\frac{a\times b}{a\cdot b}=\frac{sin\theta }{cos\theta }=tan\theta$，直接$atan2(a\times b,a\cdot b)$即可。
4.两直线交点：求直线$a,b$的交点$p$。
设点$a1,a2$确定直线$a$，点$b1,b2$确定直线$b$。
画个图发现如果能确定$\frac{|a1p|}{|a1a2|}$的值就可以了。
利用叉积代表面积的性质可以得到做法：
vec ins(line a,line b){ vec u=b1-a1,v=a2-a1,w=b2-b1; double k=(w*u)/(v*w); return a1+k*v; }
5.两线段交点：两次跨立实验判一下是不是相交。
跨立实验：$(b1-a1)\times (b1-a2)$与$(b2-a1)\times (b2-a2)$不同号，则线段$b$跨越直线$a$。
多边形相关：
1.多边形面积：$S=\frac{1}{2}\sum \limits_{i=1}^{n}P_i \times P_{i+1}$。
画一下可以发现多边形外到原点的面积恰好被算了一次正的的和一次负的，于是抵消。
2.判断点是否在多边形内：从该点出发引一条射线，如果该射线与多边形边界相交奇数次则该点在多边形内。
3.求凸包：$Graham$扫描法。
bool cmp1(node a,node b){return a.x==b.x?a.y<b.y:a.x<b.x;} bool cmp2(node a,node b){return a*b>0||(a*b==0&&dis(a)<dis(b));} void Graham(){ sort(A+1,A+1+n,cmp1); for(int i=n;i>=1;i--) A[i]=A[i]-A[1]; sort(A+2,A+1+n,cmp2); node sta[maxn]; int top=0; for(int i=1;i<=n;sta[++top]=A[i++]) while(top>=2 && (A[i]-sta[top])*(sta[top]-sta[top-1])>=0) top--; n=top; for(int i=1;i<=top;i++) A[i]=sta[i]; }
4.半平面交：给定一些有向直线，求这些直线左侧平面的交。
代码（[CQOI2006]凸多边形）：
#include<bits/stdc++.h> #define maxn 200005 #define maxm 500005 #define inf 0x7fffffff #define eps 1e-8 #define ll long long #define rint register int #define debug(x) cerr<<#x<<": "<<x<<endl #define fgx cerr<<"--------------"<<endl #define dgx cerr<<"=============="<<endl using namespace std; struct node{ double x,y; node operator+(const node t)const{return (node){x+t.x,y+t.y};} node operator-(const node t)const{return (node){x-t.x,y-t.y};} node operator^(const double t)const{return (node){x*t,y*t};} double operator*(const node t)const{return x*t.y-y*t.x;} }A[maxn],P[maxn]; struct line{ node a,b; double k,d; bool operator<(const line t)const{return (abs(k-t.k)<eps)?((b-a)*(t.b-a)>eps):(k-t.k<eps);} }que[maxn],L[maxn]; inline int read(){ int x=0,f=1; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c==‘-‘) f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-‘0‘; return x*f; } inline node ins(line l1,line l2){ node u=l2.a-l1.a,v=l1.b-l1.a,w=l2.b-l2.a; double k=(u*v)/(v*w); return l2.a+(w^k); } inline bool onr(line l,node c){return (l.b-c)*(l.a-c)>eps;} int main(){ int T=read(),n=0; while(T--){ int m=read(); for(int i=1;i<=m;i++) A[i].x=read(),A[i].y=read(); for(int i=1;i<=m;i++){ L[++n].a=A[i],L[n].b=(i==m)?A[1]:A[i+1]; L[n].k=atan2((L[n].b-L[n].a).y,(L[n].b-L[n].a).x); L[n].d=L[n].a.y-L[n].a.x*L[n].k; } } sort(L+1,L+1+n); int l=1,r=0,tot=0,cnt=0; for(int i=1;i<=n;i++) if(abs(L[i].k-L[i+1].k)>eps) L[++cnt]=L[i]; for(int i=1;i<=cnt;i++){ while(l<r && onr(L[i],ins(que[r-1],que[r]))) r--; while(l<r && onr(L[i],ins(que[l],que[l+1]))) l++; que[++r]=L[i]; } while(l<r && onr(que[l],ins(que[r-1],que[r]))) r--; while(l<r && onr(que[r],ins(que[l],que[l+1]))) l++; for(int i=l;i<=r;i++){ line l1=que[i],l2=(i==r)?que[l]:que[i+1]; P[++tot]=ins(l1,l2); } double S=0; for(int i=1;i<=tot;i++) S+=P[i]*((i==tot)?P[1]:P[i+1]); printf("%.3lf\n",(tot<=2)?0:(S*0.5)); return 0; }
5.旋转卡壳：求凸包直径（凸包上最远点对的距离）。
代码（[USACO03FALL]Beauty Contest G）：
#include<bits/stdc++.h> #define maxn 200005 #define maxm 500005 #define inf 0x7fffffff #define ll long long #define rint register ll #define debug(x) cerr<<#x<<": "<<x<<endl #define fgx cerr<<"--------------"<<endl #define dgx cerr<<"=============="<<endl using namespace std; struct node{ ll x,y; inline node operator+(const node t)const{return (node){x+t.x,y+t.y};} inline node operator-(const node t)const{return (node){x-t.x,y-t.y};} inline node operator^(const ll t)const{return (node){x*t,y*t};} inline ll operator*(const node t)const{return x*t.y-y*t.x;} }A[maxn],S[maxn]; ll n; inline ll read(){ ll x=0,f=1; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c==‘-‘) f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-‘0‘; return x*f; } inline bool cmp1(node a,node b){return (a.x==b.x)?(a.y<b.y):(a.x<b.x);} inline bool cmp2(node a,node b){return (a*b==0)?(a.x<b.x):(a*b>0);} inline ll dis(node a,node b){return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);} inline void Graham(){ sort(A+1,A+1+n,cmp1); for(ll i=n;i>=1;i--) A[i]=A[i]-A[1]; sort(A+2,A+1+n,cmp2); ll top=0; for(ll i=1;i<=n;i++){ while(top>1 && (A[i]-S[top])*(S[top]-S[top-1])>=0) top--; S[++top]=A[i]; } n=top; for(ll i=1;i<=n;i++) A[i]=S[i]; } int main(){ n=read(); for(ll i=1;i<=n;i++) A[i].x=read(),A[i].y=read(); Graham(); if(n==2){printf("%lld\n",dis(A[1],A[2]));return 0;} A[++n]=A[1]; ll res=0; for(ll i=1,j=1;i<n;i++){ while((A[i+1]-A[i])*(A[j]-A[i])<=(A[i+1]-A[i])*(A[j+1]-A[i])) j=(j%(n-1))+1; res=max(res,max(dis(A[j],A[i]),dis(A[j],A[i+1]))); } printf("%lld\n",res); return 0; }
原文：https://www.cnblogs.com/YSFAC/p/13152847.html
