计算几何笔记 (模板)

Froggy

2019-12-08 21:07:40

Personal

正弦定理:

d_{circumcircle}= \frac{a}{\sin A}=\frac{b}{\sin B}=\frac{c}{\sin C}

余弦定理:

a^2=b^2+c^2-2bc \times \cos A b^2=a^2+c^2-2ac \times \cos B c^2=a^2+b^2-2ab \times \cos C

向量旋转:

\begin{bmatrix}\cos \theta &-\sin \theta\\\sin \theta&\cos \theta\end{bmatrix} \times \begin{bmatrix}x\\y\end{bmatrix}=\begin{bmatrix}x^\prime\\y^\prime\end{bmatrix}

向量基本操作:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
#define N 100010
using namespace std;
const double eps=1e-10;
const double PI=acos(-1.0);
//Vector可以用Point来表示 
struct Point{
    double x,y;
    Point(){} Point(double _x,double _y){x=_x,y=_y;}
    //相等
    inline bool operator ==(Point b){
        return fabs(x-b.x)<=eps&&fabs(y-b.y)<=eps;
    } 
    //不相等 
    inline bool operator !=(Point b){
        return !((*this)==b);
    } 
    //相加 
    inline Point operator +(Point b){
        return Point(x+b.x,y+b.y);
    }
    //相减 
    inline Point operator -(Point b){
        return Point(x-b.x,y-b.y);
    }
    //点积 
    inline double operator *(Point b){
        return x*b.x+y*b.y;
    }
    //叉积 
    inline double operator %(Point b){
        return x*b.y-y*b.x;
    }
    //长度 
    inline double len(){
        return sqrt(x*x+y*y);
    }
    //单位向量
    inline Point unit(){
        double tmp=len();
        return Point(x/tmp,y/tmp);
    } 
    //求单位法向量 
    inline Point normal(){
        double tmp=len();
        return Point(-y/tmp,x/tmp);
    }
    //点从下往上排序
    inline bool operator <(Point b){
        return fabs(y-b.y)<eps?x<b.x:y<b.y; 
    } 
    //平面直角坐标系上半部分优先
    inline bool Quad(){
        return y>eps||(fabs(y)<=eps&&x>=-eps);
    } 
}LTL;//Lower Then Left
inline Point operator *(double k,Point a){
    return Point(a.x*k,a.y*k);
}
//两个向量的夹角 
inline double Angle(Point a,Point b){
    //return acos(a*b/a.len()/b.len());
    double tmp=atan2(b.y,b.x)-atan2(a.y,a.x); 
    while(tmp>=PI+eps)tmp-=2*PI;
    while(tmp<=-PI-eps)tmp+=2*PI;
    return tmp;
}
//判断两个向量是否平行
inline bool Para(Point a,Point b){
    return fabs(a%b)<=eps;
} 
//判断向量a是否在向量b的左侧
inline bool Left(Point a,Point b){
    return b%a>eps;
} 
//逆时针旋转p后的向量 
inline Point Rotate(Point a,double p){
    return Point(a.x*cos(p)-a.y*sin(p),a.x*sin(p)+a.y*cos(p));
}
//绕LTL逆时针排序 
inline bool cmp(Point a,Point b){
    a=a-LTL,b=b-LTL;
    return Para(a,b)?a.len()<b.len():Left(b,a);
} 

直线:

//直线 
struct Line{
    Point p[2];
    Line(){} Line(Point a,Point b){p[0]=a,p[1]=b;}
    inline Point& operator [] (int i){
        return p[i];
    }
    inline Point v(){
        return p[1]-p[0];
    }
};
//直线交点 
inline Point Cross(Line a,Line b){
    return a[0]+((b[0]-a[0])%(b[1]-a[0]))/((a[1]-a[0])%(b[1]-b[0]))*(a[1]-a[0]);
} 

多边形:

//多边形 
typedef vector<Point> Poly;
//面积 
inline double Area(Poly a){
    double tot=0;
    for(int i=0;i<a.size()-1;i++){
        tot+=a[i]%a[i+1];
    }
    tot+=a[a.size()-1]%a[0];
    return fabs(tot)/2.0;
} 
//周长
inline double C(Poly a){
    double tot=0;
    for(int i=0;i<a.size()-1;i++){
        tot+=(a[i+1]-a[i]).len();
    }
    tot+=(a[a.size()-1]-a[0]).len();
    return tot;
} 
//重心 
inline Point Cent(Poly a){
    double x=0,y=0,m=0;
    for(int i=1;i<a.size()-1;++i){
        double tmp=(a[i]-a[0])%(a[i+1]-a[0]);
        x+=tmp*(a[0].x+a[i].x+a[i+1].x)/3.0;
        y+=tmp*(a[0].y+a[i].y+a[i+1].y)/3.0;
        m+=tmp;
    }
    return Point(x/m,y/m);
} 

凸包:

//求凸包 (的周长) 
Point st[123456];
int top;
inline double Convex(Poly a){
    top=0;
    LTL=(*min_element(a.begin(),a.end()));
    sort(a.begin(),a.end(),cmp);
    for(int i=0;i<a.size();++i){
        while(top>1&&!Left(a[i]-st[top-1],st[top]-st[top-1]))--top;
        st[++top]=a[i];
    }
    Poly tmp;
    for(int i=1;i<=top;i++)tmp.push_back(st[i]);
    return C(tmp); 
}

点与多边形关系:

// 求点是否在多边形内(单次询问,可以是凹多边形)
inline bool Inside_1(Poly a,Point p){
    double tot=0;
    for(int i=0;i<a.size();++i)tot+=Angle(a[i]-p,a[(i+1)%n]-p);
    return fabs(tot)>=eps;
} 

//多组询问
inline bool Inside_2(Poly &a,Point p){
    if(p==LTL)return true;
    if(Left(p-LTL,a[a.size()-1]-LTL)||Left(a[1]-LTL,p-LTL))return false; 
    int pos=lower_bound(a.begin(),a.end()-1,p,cmp)-a.begin();
    return !Left(a[pos]-a[pos-1],p-a[pos-1])&&LTL<p;
}

半平面交:

//半平面交(HalfPlaneIntersection)
inline bool cmpang(Point a,Point b){
    return a.Quad()^b.Quad()?a.Quad()<b.Quad():Left(b,a);
}
inline bool operator <(Line a,Line b){
    return Para(a.v(),b.v())&&(a.v()*b.v()>eps)?Left(a[0]-b[0],b.v()):cmpang(a.v(),b.v());
}
Line q[N];
int l,r;
Poly HPI(Line L[],int m){
    sort(L+1,L+m+1);
    Poly R;
    r=1,q[l=1]=L[1];
    for(int i=2;i<=m;i++){
        if(!cmpang(q[r].v(),L[i].v()))continue;
        while(l<r&&Left(L[i].v(),Cross(q[r],q[r-1])-L[i][0]))--r;
        while(l<r&&Left(L[i].v(),Cross(q[l],q[l+1])-L[i][0]))++l;
        q[++r]=L[i];
    }
    while(l<r&&Left(q[l].v(),Cross(q[r],q[r-1])-q[l][0]))--r;
    while(l<r&&Left(q[r].v(),Cross(q[l],q[l+1])-q[r][0]))++l;
    q[r+1]=q[l];
    for(int i=l;i<=r;++i){
        R.push_back(Cross(q[i],q[i+1]));
    }
    return R;
}

Minkowski和:

//Minkowski
Poly Minkowski(Poly a,Poly b){
    Poly R;
    int i=0,j=0;
    R.push_back(a[0]+b[0]);
    while(1){
        if(Left(a[(i+1)%a.size()]-a[i],b[(j+1)%b.size()]-b[j])){
            j=(j+1)%b.size();
        }
        else{
            i=(i+1)%a.size();
        }
        Point tmp=a[i]+b[j];
        if(R.size()>1&&Para(tmp-R[R.size()-1],R[R.size()-1]-R[R.size()-2])){
            R.pop_back();
        }
        R.push_back(tmp);
        if(!i&&!j)break;
    }
    R.pop_back();
    return R;
}

旋转卡壳:

int RC(Poly a){
    int ans=0,j=1;
    a.push_back(a[0]);
    for(int i=0;i<a.size()-1;++i){
        while((a[i]-a[j])%(a[i+1]-a[j])<(a[i]-a[j+1])%(a[i+1]-a[j+1]))j=(j+1)%a.size();
        ans=max(ans,max((a[j]-a[i]).len(),(a[j]-a[i+1]).len()));
    }
    return ans;
}