本来是不想码的，但总是忘记一些基本操作，还是记下来比较好。
#define LD double
#define Vector Point
const LD eps=1e-7;//据说：出题的大学生们基本上都是用的这个值
inline int dcmp(LD a){return a<-eps?-1:(a>eps?1:0);}//处理精度
inline LD Abs(LD a){return a*dcmp(a);}//取绝对值
struct Point{
LD x,y;Point(LD X=0,LD Y=0){x=X,y=Y;}
inline void in(){scanf("%lf%lf",&x,&y);}
inline void out(){printf("%.2lf %.2lf\n",x,y);}
};对于 \(\vec{a}=(x,y),\) \(|\vec{a}|=\sqrt{x^2+y^2}\) \(=\sqrt{|\vec{a}|^{2}}\) \(=\sqrt{\vec{a} \cdot \vec{a}}\) 。
inline LD Len(Vector a){return sqrt(Dot(a,a));}//模长对于 \(\vec{a}=(x_{1},y_{1}),\) \(\vec{b}=(x_{2},y_{2}),\) \(\vec{a}+\vec{b}=(x_{1}+x_{2},y_{1}+y_{2})\) 。
对于 \(\vec{a}=(x_{1},y_{1}),\) \(\vec{b}=(x_{2},y_{2}),\) \(\vec{a}-\vec{b}=(x_{1}-x_{2},y_{1}-y_{2})\) 。
inline Vector operator+(Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y);}
inline Vector operator-(Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);}对于 \(\vec{a}=(x,y),\) \(\lambda \vec{a}=(\lambda x,\lambda y)\) 。
除法也可以理解为数乘：\(\frac{\vec{a}}{\lambda}=\frac{1}{\lambda}\vec{a}=(\frac{1}{\lambda} x,\frac{1}{\lambda} y)\) 。
inline Vector operator*(Vector a,LD b){return Vector(a.x*b,a.y*b);}\(\vec{a} \cdot \vec{b}=|\vec{a}||\vec{b}| \cos \theta\) \((\theta=\langle\vec{a}, \vec{b}\rangle)\) 。
对于 \(\vec{a}=(x_{1}, y_{1}), \vec{b}=(x_{2}, y_{2}),\) \(\vec{a} \cdot \vec{b}=x_{1} x_{2}+y_{1} y_{2}\) 。
夹角 \(\theta\) 与点积大小的关系：
\((1).\) 若 \(\theta=0^{\circ},\) \(\vec{a} \cdot \vec{b}=|\vec{a}||\vec{b}|\) 。
\((2).\) 若 \(\theta=180^{\circ},\) \(\vec{a} \cdot \vec{b}=-|\vec{a}||\vec{b}|\) 。
\((3).\) 若 \(\theta < 90^{\circ},\) \(\vec{a} \cdot \vec{b}>0\) 。
\((4).\) 若 \(\theta=90^{\circ},\) \(\vec{a} \cdot \vec{b}=0\) 。
\((5).\) 若 \(\theta > 90^{\circ},\) \(\vec{a} \cdot \vec{b}<0\) 。
inline LD Dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}//点积\(\vec{a} \times \vec{b}=|\vec{a}||\vec{b}| \cos \theta\) \((\theta=\langle\vec{a}, \vec{b}\rangle)\) 。
对于 \(\vec{a}=(x_{1}, y_{1}), \vec{b}=(x_{2}, y_{2}),\) \(\vec{a} \times \vec{b}=x_{1} y_{2}-y_{1} x_{2}\) 。
向量位置与叉积大小的关系：
\((1).\) 若 \(\vec{a} \| \vec{b},\) \(\vec{a} \times \vec{b}=0\) 。
\((2).\) 若 \(\vec{a}\) 在 \(\vec{b}\) 右侧，\(\vec{a} \times \vec{b}>0\) 。
\((3).\) 若 \(\vec{a}\) 在 \(\vec{b}\) 左侧，\(\vec{a} \times \vec{b}<0\) 。
inline LD Cro(Vector a,Vector b){return a.x*b.y-a.y*b.x;}//叉积对于点 \(P=(x,y)\) 或向量 \(\vec{a}=(x,y)\)，将其逆时针旋转 \(\theta\) 角度（点：关于原点，向量：关于起点）： \(\begin{vmatrix}x&y\end{vmatrix}\) \(\times\) \(\begin{vmatrix}cos \theta & sin \theta\\ -sin \theta & cos \theta \end{vmatrix}\) \(=\) \(\begin{vmatrix}xcos \theta -ysin \theta &xsin \theta + ycos \theta \end{vmatrix}\) 。
将点 \(A(x,y)\) 绕点 \(B(x_0,y_0)\) 旋转旋转 \(\theta\) 角度：\(\begin{vmatrix}(x\!-\!x_0)cos \theta -(y\!-\!y_0)sin \theta + x_0 &(x\!-\!x_0)sin \theta + (y\!-\!y_0)cos \theta + y_0 \end{vmatrix}\) 。
inline Point turn_PP(Point a,Point b,LD theta){//点A绕点B旋转theta(弧度)
LD x=(a.x-b.x)*cos(theta)+(a.y-b.y)*sin(theta)+b.x;
LD y=-(a.x-b.x)*sin(theta)+(a.y-b.y)*cos(theta)+b.y;
return Point(x,y);
}\((1).\) 判断点 \(P\) 是否在线段 \(AB\) 上：
inline int pan_PL(Point p,Point a,Point b){//判断点P是否在线段AB上
return !dcmp(Cro(p-a,b-a))&&min(a.x,b.x)<=p.x&&p.x<=max(a.x,b.x)&&min(a.y,b.y)<=p.y&&p.y<=max(a.y,b.y);
//PA,AB共线且P在AB之间
}\((2).\) 点 \(P\) 到线段 \(AB\) 的距离：
【模板】 \(\text{Railway}\) \(\text{[Uva10263]}\)
【题解】 \(\text{Xing_Ling}\)
inline bool operator==(Point a,Point b){return !dcmp(a.x-b.x)&&!dcmp(a.y-b.y);}//两点坐标重合则相等
inline LD dis_PL(Point p,Point a,Point b{//点P到线段AB距离
if(a==b)return Len(p-a);//AB重合
Vector x=p-a,y=p-b,z=b-a;
if(dcmp(Dot(x,z))<0)return Len(x);//P距离A更近
if(dcmp(Dot(y,z))>0)return Len(y);//P距离B更近
return Abs(Cro(x,z)/Len(z));//Len(x)*sin(θ)
}\((1).\) 点 \(P\) 到直线 \(AB\) 的垂足 \(F\)：
inline Point FootPoint(Point p,Point a,Point b){//点P到直线AB的垂足
Vector x=p-a,y=p-b,z=b-a;
LD len1=Dot(x,z)/Len(z),len2=-1.0*Dot(y,z)/Len(z);//分别计算AB在投影
return a+z*(len1/(len1+len2));//点A加上向量AF
}\((2).\) 点 \(P\) 关于直线 \(AB\) 的对称点：
inline Point Symmetry_PL(Point p,Point a,Point b){//点P关于直线AB的对称点
return p+(FootPoint(p,a,b)-p)*2;//将PF延长一倍即可
}\((1).\) 判断两线段 \(AB,CD\) 是否相交：
inline int pan_cross_LL(Point a,Point b,Point c,Point d){//判断两线段AB,CD是否相交
LD c1=Cro(b-a,c-a),c2=Cro(b-a,d-a);
LD d1=Cro(d-c,a-c),d2=Cro(d-c,b-c);
return dcmp(c1)*dcmp(c2)<0&&dcmp(d1)*dcmp(d2)<0;//分别在两侧
}\((2).\) 两线段 \(AB,CD\) 的交点 \(Q\)：
inline Point cross_LL(Point a,Point b,Point c,Point d){//两线段AB,CD的交点
Vector x=b-a,y=d-c,z=a-c;
return a+x*(Cro(y,z)/Cro(x,y));//点A加上向量AQ
}\((1).\) 判断点 \(A\) 是否在任意多边形 \(Poly\) 以内（射线法）：
【模板】 \(\text{Cupid's Arrow}\) \(\text{[Hdu1756]}\)
inline int PIP(Point *P,Re n,Point a){//判断点A是否在任意多边形Poly以内（射线法）
Re cnt=0;LD tmp;
for(Re i=1;i<=n;++i){
Re j=i<n?i+1:1;
if(pan_PL(a,P[i],P[j]))return 2;//点在多边形上
if(a.y>=min(P[i].y,P[j].y)&&a.y<max(P[i].y,P[j].y))//纵坐标在该线段两端点之间
tmp=P[i].x+(a.y-P[i].y)/(P[j].y-P[i].y)*(P[j].x-P[i].x),cnt+=dcmp(tmp-a.x)>0;//交点在A右方
}
return cnt&1;//穿过奇数次则在多边形以内
}\((2).\) 判断点 \(A\) 是否在凸多边形 \(Poly\) 以内（二分法）：
【模板】 凸多边形 \(\text{[hrbust1429]}\)
inline int judge(Point a,Point L,Point R){//判断点AL是否在AR右边
return dcmp(Cro(L-a,R-a))>0;//必须严格以内
}
inline int PIP_(Point *P,Re n,Point a){//判断点A是否在凸多边形Poly以内（二分法）
//点按顺时针给出
if(judge(P[1],P[2],a)||judge(P[1],a,P[n]))return 0;//在P[1_2]或P[1_n]外
if(pan_PL(a,P[1],P[2])||pan_PL(a,P[1],P[n]))return 2;//在P[1_2]或P[1_n]上
Re L=2,R=n-1;
while(L<R){//二分找到一个位置pos使得P[1]_A在P[1_pos],P[1_(pos+1)]之间
Re mid=L+R+1>>1;
if(judge(P[1],a,P[mid]))L=mid;
else R=mid-1;
}
if(judge(P[L],P[L+1],a))return 0;//在P[pos_(pos+1)]外
if(pan_PL(a,P[L],P[L+1]))return 2;//在P[pos_(pos+1)]上
return 1;
}\((1).\) 判断线段 \(AB\) 是否在任意多边形 \(Poly\) 以内：不相交且两端点 \(A,B\) 均在多边形以内。
\((2).\) 判断线段 \(AB\) 是否在凸多边形 \(Poly\) 以内：两端点 \(A,B\) 均在多边形以内。
\((1).\) 判断任意两个多边形是否相离：属于不同多边形的任意两边都不相交 且 一个多边形上的任意点都不被另一个多边形所包含。
【模板】 \(\text{The Great Divide [Uva10256]}\)
【题解】 \(\text{Xing_Ling}\)
原文：https://www.cnblogs.com/Xing-Ling/p/12102489.html