计算几何模板一（点、线段、直线）

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define Sgn(x) (((x)<0)?(-1):(1))
#define eps 1e-8
#define INF 1e10
#define Pi (acos(-1.0))
double Deg2Rad(double deg) {return (deg*Pi/180.0);}
double Rad2Deg(double rad) {return (rad*180.0/Pi);}
double Sin(double deg) {return sin(Deg2Rad(deg));}
double Cos(double deg) {return cos(Deg2Rad(deg));}
double ArcSin(double val) {return Rad2Deg(asin(val));}
double ArcCos(double val) {return Rad2Deg(acos(val));}

//点
struct POINT
{
    double x,y;
    POINT():x(0),y(0){}
    POINT(double _x,double _y):x(_x),y(_y){};
};

//两个点的距离
double Distance(const POINT &a,const POINT &b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

//线段
struct SEG
{
    POINT a;//起点
    POINT b;//终点
    SEG(){};
    SEG(POINT _a,POINT _b):a(_a),b(_b){};
};

//直线（两点式）
struct LINE
{
    POINT a,b;
    LINE(){};
    LINE(POINT _a,POINT _b):a(_a),b(_b){};
};

//直线（一般式）
struct LINE2
{
    double A,B,C;
    LINE2(){};
    LINE2(double _A,double _B,double _C):A(_A),B(_B),C(_C){};
};

//两点式化一般式
LINE2 Line2line(const LINE &L)
{
    LINE2 L2;
    L2.A=L.b.y-L.a.y;
    L2.B=L.a.x-L.b.x;
    L2.C=L.b.x*L.a.y-L.a.x*L.b.y;
    return L2;
}

//返回直线Ax+By+C=0的系数
void Coefficient(const LINE &L,double &A,double &B,double &C)
{
    A=L.b.y-L.a.y;
    B=L.a.x-L.b.x;
    C=L.b.x*L.a.y-L.a.x*L.b.y;
}

void Coefficient(const POINT &p,const double a,double &A,double &B,double &C)
{
    A=Cos(a);
    B=Sin(a);
    C=-(p.y*B+p.x*A);
}

//直线相交的交点
POINT Intersection(const LINE &A,const LINE &B)
{
    double A1,B1,C1;
    double A2,B2,C2;
    Coefficient(A,A1,B1,C1);
    Coefficient(B,A2,B2,C2);
    POINT I(0,0);
    I.x=-(B2*C1-B1*C2)/(A1*B2-A2*B1);
    I.y= (A2*C1-A1*C2)/(A1*B2-A2*B1);
    return I;
}

//点到直线的距离
double Ptol(const POINT p,const LINE2 L)
{
    return fabs(L.A*p.x+L.B*p.y+L.C)/sqrt(L.A*L.A+L.B*L.B);
}

//两线段叉乘
double Cross2(const SEG &p,const SEG &q)
{
    return (p.b.x-p.a.x)*(q.b.y-q.a.y)-(q.b.x-q.a.x)*(p.b.y-p.a.y);
}

//有公共端点o叉乘，并判拐，若正p0->p1->p2拐向左
double Cross(const POINT &a,const POINT &b,const POINT &o)
{
    return (a.x-o.x)*(b.y-o.y)-(b.x-o.x)*(a.y-o.y);
}

//判等（值，点，直线）
bool IsEqual(double a,double b)
{
    return (abs(a-b)<eps);
}
bool IsEqual(const POINT &a,const POINT &b)
{
    return (IsEqual(a.x,b.x)&&IsEqual(a.y,b.y));
}
bool IsEqual(const LINE &A,const LINE &B)
{
    double A1,B1,C1;
    double A2,B2,C2;
    Coefficient(A,A1,B1,C1);
    Coefficient(B,A2,B2,C2);
    return IsEqual(A1*B2,A2*B1)&&
           IsEqual(A1*C2,A2*C1)&&
           IsEqual(B1*C2,B2*C1);
}

//判断点是否在线段上
bool IsOnSeg(const SEG &seg,const POINT &p)
{
    return (IsEqual(p,seg.a)||IsEqual(p,seg.b))||
           (((p.x-seg.a.x)*(p.x-seg.b.x)<0||
             (p.y-seg.a.y)*(p.y-seg.b.y)<0)&&
             (IsEqual(Cross(seg.b,p,seg.a),0)));
}

//判断两条线段是否相交，端点重合算相交
bool IsIntersect(const SEG &u,const SEG &v)
{
    return (Cross(v.a,u.b,u.a)*Cross(u.b,v.b,u.a)>=0)&&
           (Cross(u.a,v.b,v.a)*Cross(v.b,u.b,v.a)>=0)&&
           (max(u.a.x,u.b.x)>=min(v.a.x,v.b.x))&&
           (max(v.a.x,v.b.x)>=min(u.a.x,u.b.x))&&
           (max(u.a.y,u.b.y)>=min(v.a.y,v.b.y))&&
           (max(v.a.y,v.b.y)>=min(u.a.y,u.b.y));
}

//判断线段P和直线Q是否相交，端点重合算相交
bool IsOnLine(const SEG &p,const LINE &q)
{
    SEG p1,p2,q0;
    p1.a=q.a;p1.b=p.a;
    p2.a=q.a;p2.b=p.b;
    q0.a=q.a;q0.b=q.b;
    return (Cross2(p1,q0)*Cross2(q0,p2)>=0);
}

//判断两条线段是否平行
bool IsParallel(const LINE &A,const LINE &B)
{
    double A1,B1,C1;
    double A2,B2,C2;
    Coefficient(A,A1,B1,C1);
    Coefficient(B,A2,B2,C2);
    //共线不算平行
    /*return (A1*B2==A2*B1)&&
    ((A1*C2!=A2*C1)||(B1*C2!=B2*C1));*/
    //共线算平行
    return (A1*B2==A2*B1);
}

//判断两条直线是否相交
bool IsIntersect(const LINE &A,const LINE &B)
{
    return !IsParallel(A,B);
}