计算几何

计算几何模板
持续整理ing…

const double eps=1e-8;
int sgn(double x)
{
    if(x>eps) return 1;
    if(x<-eps) return -1;
    return 0;
}
inline double add(double a,double b)
{
    if(abs(a+b)<eps*(abs(a)+abs(b))) return 0;
    return a+b;
}
struct Point{
    double x,y;
    Point(double x=0,double y=0) :x(x),y(y) {}
    Point operator + (Point p) {return Point(x+p.x,y+p.y);}
    Point operator - (Point p) {return Point(x-p.x,y-p.y);}
    Point operator * (double d){return Point(x*d,y*d);}
    //bool operator < (Point p)  {return x!=p.x?x<p.x:y<p.y;}
    Point ver() {return Point(-y,x);}    //垂直向量 
};
double dot(Point p1,Point p2) {return p1.x*p2.x+p1.y*p2.y;} //内积
double cross(Point p1,Point p2) {return add(p1.x*p2.y,-p2.x*p1.y);}  //外积
bool on_seg(Point p1,Point p2,Point p)    //判断点p在线段上 
{
    return sgn(cross(p1-p,p2-p))==0&&sgn(dot(p1-p,p2-p))<=0;
}
Point intersection(Point p1,Point p2,Point q1,Point q2)   //求两直线交点 
{
    return p1+(p2-p1)*(cross(q2-q1,q1-p1)/cross(q2-q1,p2-p1));
}
bool same_side(Point p1,Point p2,Point q1,Point q2)
{
    int A=p2.y-p1.y,B=p1.x-p2.x,C=p2.x*p1.y-p1.x*p2.y;
    return sgn((A*q1.x+B*q1.y+C)*(A*q2.x+B*q2.y+C))<0;
}
int leftright(Point p1,Point p2,Point p3)
{
    double num_det=p1.x*p2.y+p3.x*p1.y+p2.x*p3.y-p3.x*p2.y-p2.x*p1.y-p1.x*p3.y;
    return sgn(num_det); //返回值为1,p3在直线p1p2左侧;-1在右侧;0在直线上 
}
int convexHull(Point *P,int n,Point *aim)  //凸包，m为凸包顶点数，aim保存凸包顶点，P为所有点集 
{
    int i,m=0;
    sort(P+1,P+1+n,cmp);
    for(i=1;i<=n;i++)
    {
        while(m>=2&&cross(aim[m]-aim[m-1],P[i]-aim[m-1])<=0) m--;
        aim[++m]=P[i];
    }
    int k=m;
    for(i=n-1;i>=0;i--)
    {
        while(m>k&&cross(aim[m]-aim[m-1],P[i]-aim[m-1])<=0) m--;
        aim[++m]=P[i];
    }
    return m;
}