$摘自辰星凌大佬的博客，并加上自己的想法简化了一下$

定义

struct Point{
    double x,y;Point(double X=0,double Y=0){x=X,y=Y;}
};
const double eps=1e-8;
int dcmp(double a){return a<-eps?-1:(a>eps?1:0);}//处理精度
double Abs(double a){return a*dcmp(a);}//取绝对值

模长

$对于\vec{a} = (x,y),\left\vert a\right\vert=\sqrt{x^2+y^2}=\sqrt{\left\vert\vec{a}\right\vert^2}$

double Len(Point a){return sqrt(a.x*a.x+a.y+a.y);}//模长

向量加减

$对于\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)$

Point operator+(Point a,Point b){return Point(a.x+b.x,a.y+b.y);}
Point operator-(Point a,Point b){return Point(a.x-b.x,a.y-b.y);}

向量数乘

$对于\vec{a} = (x,y),λ\vec{a}=(λx,λy)$
$除法也可以理解为数乘:\frac{\vec{a}}{λ}=(\frac{1}{λ}x,\frac{1}{λ}y)$

Point operator*(Point a,double b){return Point(a.x*b,a.y*b);}

点积

$\vec{a}\cdot\vec{b}=\left\vert a\right\vert \left\vert b\right\vert cosθ (θ=<\vec{a},\vec{b}>)$
$对于\vec{a} = (x_1,y_1),\vec{b} = (x_2,y_2),\vec{a}\cdot\vec{b}=x_1x_2+y_1y_2$
$夹角 θ 与点积大小的关系：$
$若θ=0^\circ,\vec{a}\cdot\vec{b}=\left\vert\vec{a}\right\vert\left\vert\vec{b}\right\vert$
$若θ=180^\circ,\vec{a}\cdot\vec{b}=-\left\vert\vec{a}\right\vert\left\vert\vec{b}\right\vert$
$若θ<90^\circ,\vec{a}\cdot\vec{b}>0$
$若θ=90^\circ,\vec{a}\cdot\vec{b}=0$
$若θ>90^\circ,\vec{a}\cdot\vec{b}<0$

double Dot(Point a,Point b){return a.x*b.x+a.y*b.y;}//点积

叉积

$对于\vec{a} = (x_1,y_1),\vec{b} = (x_2,y_2),\vec{a}\times\vec{b}=x_1y_2-x_2y_1$
$向量位置与叉积大小的关系：$
$若\vec{a} || \vec{b},\vec{a} \times \vec{b}=0$
$若\vec{a}在\vec{b}的右侧,\vec{a} \times \vec{b}>0$
$若\vec{a}在\vec{b}的左侧,\vec{a} \times \vec{b}<0$

double Cro(Point a,Point b){return a.x*b.y-a.y*b.x;}//叉积

点、向量的位置变换

点、向量的旋转

$(1).对于点P(x,y) 或 向量\vec{a}=(x,y),将其顺时针旋转θ角度（点：关于原点，向量：关于起点）:$
$\begin{vmatrix}x&y\end{vmatrix} \times \begin{vmatrix}cosθ&−sinθ\\\sinθ&cosθ\end{vmatrix} = \begin{vmatrix}xcosθ &+&ysinθ &-&xsinθ &+&ycosθ \end{vmatrix}$

Point turn_P(Point a,double theta){//点A\向量A顺时针旋转theta(弧度)
    double x=a.x*cos(theta)+a.y*sin(theta);
    double y=-a.x*sin(theta)+a.y*cos(theta);
    return Point(x,y);
}

$(2).将点 A(x,y) 绕点 B(x_0,y_0) 顺时针旋转 θ 角度：$
$\begin{vmatrix}(x−x_0)cosθ &+&(y−y_0)sinθ+x_0 &-&(x−x_0)sinθ &+&(y−y_0)cosθ&+&y_0 \end{vmatrix}$

Point turn_PP(Point a,Point b,double theta){//将点A绕点B顺时针旋转theta(弧度)
    double x=(a.x-b.x)*cos(theta)+(a.y-b.y)*sin(theta)+b.x;
    double y=-(a.x-b.x)*sin(theta)+(a.y-b.y)*cos(theta)+b.y;
    return Point(x,y);
}

图形与图形之间的关系

点与线段

$(1). 判断点 P 是否在线段 AB 上：$

int pan_PL(Point p,Point a,Point b){//判断点P是否在线段AB上
    return !dcmp(Cro(p-a,b-a))&&dcmp(Dot(p-a,p-b))<=0;
}

$(2). 点 P 到线段 AB 的距离：$

bool operator==(Point a,Point b){return !dcmp(a.x-b.x)&&!dcmp(a.y-b.y);}//两点坐标重合则相等
double dis_PL(Point p,Point a,Point b){//点P到线段AB距离
    if(a==b)return Len(p-a);//AB重合
    Point 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));//面积除以底边长
}

点与直线

$(1). 判断点 P 是否在直线 AB 上：$

int pan_PL_(Point p,Point a,Point b){//判断点P是否在直线AB上
    return !dcmp(Cro(p-a,b-a));//PA,AB共线
}

$(2). 点 P 到直线 AB 的垂足 F：$

Point FootPoint(Point p,Point a,Point b){//点P到直线AB的垂足
    Point x=p-a,y=p-b,z=b-a;
    double len1=Dot(x,z)/Len(z),len2=-1.0*Dot(y,z)/Len(z);//分别计算AP,BP在AB,BA上的投影
    return a+z*(len1/(len1+len2));//点A加上向量AF
}

$(3). 点 P 关于直线 AB 的对称点：$

Point Symmetry_PL(Point p,Point a,Point b){//点P关于直线AB的对称点
    return p+(FootPoint(p,a,b)-p)*2;//将PF延长一倍即可
}

线与线

$(1). 两直线 AB,CD 的交点 Q：$

Point cross_LL(Point a,Point b,Point c,Point d){//两直线AB,CD的交点
    Point x=b-a,y=d-c,z=a-c;
    return a+x*(Cro(y,z)/Cro(x,y));//点A加上向量AF
}

$(2). 判断直线 AB 与线段 CD 是否相交：$

int pan_cross_L_L(Point a,Point b,Point c,Point d){//判断直线AB与线段CD是否相交
    return pan_PL(cross_LL(a,b,c,d),c,d);//直线AB与直线CD的交点在线段CD上
}

$(3). 判断两线段 AB,CD 是否相交：$

int pan_cross_LL(Point a,Point b,Point c,Point d){//判断两线段AB,CD是否相交
    double c1=Cro(b-a,c-a),c2=Cro(b-a,d-a);
    double d1=Cro(d-c,a-c),d2=Cro(d-c,b-c);
    return dcmp(c1)*dcmp(c2)<0&&dcmp(d1)*dcmp(d2)<0;//分别在两侧
}

点与多边形

$(1). 判断点 A 是否在任意多边形 Poly 以内（射线法）：$

int PIP(Point *P,int n,Point a){//[射线法]判断点A是否在任意多边形Poly以内
    int cnt=0;double tmp;
    for(int i=1;i<=n;++i){
        int 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 以内（二分法）：$

int judge(Point a,Point L,Point R){//判断AL是否在AR右边
    return dcmp(Cro(L-a,R-a))>0;//必须严格以内
}
int PIP_(Point *P,int n,Point a){//[二分法]判断点A是否在凸多边形Poly以内
    //点按逆时针给出
    if(judge(P[1],a,P[2])||judge(P[1],P[n],a))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]上
    int l=2,r=n-1;
    while(l<r){//二分找到一个位置pos使得P[1]_A在P[1_pos],P[1_(pos+1)]之间
        int mid=l+r+1>>1;
        if(judge(P[1],P[mid],a))l=mid;
        else r=mid-1;
    }
    if(judge(P[l],a,P[l+1]))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). 判断任意两个多边形是否相离：属于不同多边形的任意两边都不相交 且 一个多边形上的任意点都不被另一个多边形所包含。$

int judge_PP(Point *A,int n,Point *B,int m){//[判断多边形A与多边形B是否相离]
    for(int i1=1;i1<=n;++i1){
        int j1=i1<n?i1+1:1;
        for(int i2=1;i2<=m;++i2){
            int j2=i2<m?i2+1:1;
            if(pan_cross_LL(A[i1],A[j1],B[i2],B[j2]))return 0;//两线段相交
            if(PIP(B,m,A[i1])||PIP(A,n,B[i2]))return 0;//点包含在内
        }
    }
    return 1;
}

图形面积

任意多边形面积

double PolyArea(Point *P,int n){//[任意多边形P的面积] 
    double S=0;
    for(int i=1;i<=n;++i)S+=Cro(P[i],P[i<n?i+1:1]);
    return S/2.0;
}

匹克定理

$每个点都必须在整数点上$

$S=a(多边形内整点个数)+\dfrac{b(多边形上的整点个数)}{2} -1$

任意三点组成的面积

//A, B:直线上一点,C:待判断关系的点
int relation(Point A, Point B, Point C)
{
    // 1 left -1 right 0 in
    int c = sgn(Cross((B - A), (C - A)));
    if(c < 0) return 1;
    else if(c > 0) return -1;
    return 0;
}

圆

三点确定一圆

$(1). 暴力解方程：$
$设 x^2+y^2+Dx+Ey+F=0，圆心为 O，半径为 r，带入三点 A(x_1,y_1),B(x_2,y_2),C(x_3,y_3)，解得：$
$$\begin{cases}D=\dfrac{(x_2^2+y_2^2−x_3^2−y_3^2)(y_1−y_2)−(x_1^2+y_1^2−x_2^2−y_2^2)(y_2−y_3)}{(x_1−x_2)(y_2−y_3)−(x_2−x_3)(y_1−y_2)}\\\E=\dfrac{x_1^2+y_1^2−x_2^2−y_2^2+D(x_1−x_2)}{y_2-y_1} \\\F=−(x_1^2+y_1^2+D_{x1}+E_{y1})\\\O=(-\dfrac{D}{2},-\dfrac{E}{2})\\\r=\dfrac{D^2+E^2-4F}{4} \end{cases}$$

#define S(a) ((a)*(a))
struct Circle{Point O;double r;Circle(Point P,double R=0){O=P,r=R;}};
Circle getCircle(Point A,Point B,Point C){//[三点确定一圆]暴力解方程
    double x1=A.x,y1=A.y,x2=B.x,y2=B.y,x3=C.x,y3=C.y;
    double D=((S(x2)+S(y2)-S(x3)-S(y3))*(y1-y2)-(S(x1)+S(y1)-S(x2)-S(y2))*(y2-y3))/((x1-x2)*(y2-y3)-(x2-x3)*(y1-y2));
    double E=(S(x1)+S(y1)-S(x2)-S(y2)+D*(x1-x2))/(y2-y1);
    double F=-(S(x1)+S(y1)+D*x1+E*y1);
    return Circle(Point(-D/2.0,-E/2.0),sqrt((S(D)+S(E)-4.0*F)/4.0));
}

$(2).向量求三角形垂心：$

最小覆盖圆

$【定理】 如果点 p 不在集合 {S} 的最小覆盖圆内，则 p 一定在 {S}∪p 的最小覆盖圆上。$