acm计算几何模板

大神的模板，太多了，慢慢往上敲ing

const int maxn = 1e6;
const double INF = 0x3f3f3f3f;
const int MOD = 1e9+7;
const int eps = 1e-8;

const double inf=1e20;
const double pi = acos(-1.0);
const int maxp = 1010;
//Compares a double to zero
int sgn(double x){
    if(fabs(x) < eps) return 0;
    if(x < 0)return -1;
    else return 1;
}

inline double sqr(double x){return x*x;}

struct Point{
    double x,y;
    Point(){}
    Point(double _x,double _y){x = _x,y = _y;}
    void input(){scanf("%lf%lf",&x,&y);}
    void output(){printf("%.2f %.2f\n",x,y);}
    bool operator == (Point b)const{return sgn(x-b.x) == 0 && sgn(y-b.y) == 0;}
    bool operator < (Point b)const{return sgn(x-b.x) == 0 ? sgn(y-b.y)<0 : x<b.x;}
    Point operator -(const Point &b)const{return Point(x-b.x,y-b.y);}
    double operator ^ (const Point &b)const{return x*b.y-y*b.x;}    //叉积
    double operator * (const Point &b)const{return x*b.x+y*b.y;}    //点积
    double len(){return hypot(x,y);}                                //返回长度
    double len2(){return x*2+y*y;}                                  //返回长度平方
    double distance(Point p){return hypot(x-p.x,y-p.y);}            //返回两点间距离
    Point operator + (const Point &b)const{return Point(x+b.x,y+b.y);}//
    Point operator * (const double &k)const{return Point(x*k,y*k);} //
    Point operator / (const double &k)const{return Point(x/k,y/k);} //
    double rad(Point a,Point b){Point p = *this;return fabs(atan2(fabs((a-p)^(b-p)),(a-p)^(b-p)));} //计算该点看a,b点的角度
    Point trunc(double r){  //化为长度为r的向量
        double l = len();
        if(!sgn(l)) return *this;
        r /= l;
        return Point(x*r,y*r);    
    }
    Point rotleft(){return Point(-y,x);}                             //逆时针转90度
    Point rotright(){return Point(y,-x);}                            //顺时针转90度
    Point rotate(Point p,double angle){                              //绕p点逆时针转angle
        Point v = (*this)-p;
        double c = cos(angle),s = sin(angle);
        return Point(p.x+v.x*c-v.y*s,p.y+v.x*s+v.y*c);
    }
};

struct Line{
    Point s,e;
    Line(){}
    Line(Point _s,Point _e){s = _s;e = _e;}
    bool operator == (Line v){return (s == v.s) && (e == v.e);}
    Line(Point p,double angle){                                     //根据一个点和倾斜角angle确定直线，0<=angle<=pi
        s = p;
        if(sgn(angle-pi/2) == 0){e = (s+Point(0,1));}
        else{e = (s+Point(1,tan(angle)));}
    }
    Line(double a,double b,double c){                               //ax+by+c=0
        if(sgn(a) == 0){s = Point(0,-c/b);e=Point(1,-c/b);}
        else if(sgn(b) == 0){s = Point(-c/a,0);e = Point(-c/a,1);}
        else{s = Point(0,-c/b);e = Point(1,(-c-a)/b);}
    }
    void input(){s.input();e.input();}                              
    void adjust(){if(e < s) swap(s,e);}
    double length(){return s.distance(e);}                          //求线段长度
    double angle(){                                                 //返回直线倾斜角0<=angle<=pi
        double k = atan2(e.y-s.y,e.x-s.x);
        if(sgn(k)<0) k+=pi;
        if(sgn(k-pi)==0) k-= pi;
        return k;
    }
    int relation(Point p){                                          //点和直线的关系，1在左侧，2在右侧，3在直线上
        int c = sgn((p-s)^(e-s));
        if(c < 0)return 1;
        else if(c > 0) return 2;
        else return 3;
    }
    bool  pointonseg(Point p){return sgn((p-s)^(e-s)) == 0 && sgn((p-s)^(e-s)) <= 0;}   //点在线段上的判断
    bool parallel(Line v){return sgn((e-s)^(v.e-v.s)) == 0;}        //两向量平行（对应直线平行或重合）
    int segcrosseg(Line v){                                         //两线段相交判断，2规范相交，1非规范相交，0不相交
        int d1 = sgn((e-s)^(v.s-s));
        int d2 = sgn((e-s)^(v.e-s));
        int d3 = sgn((v.e-v.s)^(s-v.s));
        int d4 = sgn((v.e-v.s)^(e-v.s));
        if((d1^d2) == -2 && (d3^d4) == -2)return 2;
        return (d1 == 0 && sgn((v.s-s)*(v.s-e)) <= 0) || 
               (d2 == 0 && sgn((v.e-s)*(v.e-e)) <= 0) ||
               (d3 == 0 && sgn((s-v.s)*(s-v.e)) <= 0) ||
               (d4 == 0 && sgn((e-v.s)*(e-v.e)) <= 0);
    }
    int linecrossseg(Line v){                                       //直线和线段相交判断，2规范相交，1非规范相交，0不相交
        int d1 = sgn((e-s)^(v.s-s));
        int d2 = sgn((e-s)^(v.e-s));
        if((d1^d2) == -2) return 2;
        return (d1 == 0 || d2 == 0);
    }
    int linecrossline(Line v){                                      //两直线关系，0平行，1重合，2相交
        if((*this).parallel(v)) return v.relation(s) == 3;
        return 2;
    }
    Point crosspoint(Line v){                                       //求两直线焦点，要保证两直线不平行或重合
        double a1 = (v.e-v.s)^(s-v.s);
        double a2 = (v.e-v.s)^(e-v.s);
        return Point((s.x*a2-e.x*a1)/(a2-a1),(s.y*a2-e.y*a1)/(a2-a1));
    }
    double dispointtoline(Point p){return fabs((p-s)*(e-s))/length();}  //点到直线的距离
    double dispointtoseg(Point p){                                  //点到线段的距离
        if(sgn((p-s)*(e-s)) < 0 || sgn((p-e)*(s-e)) < 0)
            return min(p.distance(s),p.distance(e));
        return dispointtoline(p);
    }
    double dissegtoseg(Line v){                                     //线段到线段的距离，前提是两线段不相交，相交距离为0
        return min(min(dispointtoseg(v.s),dispointtoseg(v.e)),min(v.dispointtoseg(s),v.dispointtoseg(e)));
    }
    Point lineprog(Point p){return s+(((e-s)*((e-s)*(p-s)))/((e-s).len2()));}   //返回点p在直线上的投影
    Point symmetypoint(Point p){Point q = lineprog(p);return Point(2*q.x-p.x,2*q.y-p.y);}   //返回点p关于直线的对称点
};
//圆
struct  circle
{
    Point p;
    double r;
    circle(){}
    circle(Point _p,double _r){p = _p;r = _r;}
    circle(double x,double y,double _r){p = Point(x,y);r = _r;}
    circle(Point a,Point b,Point c){                                 //三角形外接圆，需要Point的+/rotate()以及line的crosspoint()。利用两边中垂线得圆心
        Line u = Line((a+b)/2,((a+b)/2)+((b-a).rotleft()));
        Line v = Line((b+c)/2,((b+c)/2)+((c-b).rotleft()));
        p = u.crosspoint(v);
        r = p.distance(a);
    }
    circle(Point a,Point b,Point c,bool t){                          //三角形内切圆,参数bool t无作用，只是与外接圆区别  
        Line u,v;
        double m = atan2(b.y-a.y,b.x-a.x),n = atan2(c.y-a.y,c.x-a.x);
        u.s = a,v.s = b;
        u.e = u.s+Point(cos((n+m)/2),sin((n+m)/2));
        m = atan2(a.y-b.y,a.x-b.x),n = atan2(c.y-b.y,c.x-b.x);
        v.e = v.s+Point(cos((n+m)/2),sin((n+m)/2));
        p = u.crosspoint(v);
        r = Line(a,b).dispointtoseg(p);
    }
    void input(){p.input;scanf("%lf",&r);}
    void output(){printf("%.2lf %.2lf %.2lf\n",p.x,p.y,r);}
    bool operator == (circle v)const{return (p==v.p) && sgn(r-v.r) == 0;}
    bool operator < (circle v)const{return ((p<v.p) || ((p==v.p) && sgn(r-v.r) < 0));}
    double area(){return pi*r*r;}                                     //返回面积
    double circumference(){return 2*pi*r;}                            //返回周长
    int relation(Point b){                                            //点和圆的关系，0圆外，1圆上，2圆内
        double dst = b.distance(p);
        if(sgn(dst-r) < 0)return 2;
        else if(sgn(dst-r) == 0)return 1;
        else return 0;
    }
    int relationseg(Line v){                                          //线段和圆的关系，比较的是圆心到线段的距离和半径的关系
        double dst = v.dispointtoseg(p);
        if(sgn(dst-r) < 0)return 2;
        else if(sgn(dst-r) == 0)return 1;
        else return 0;
    }
    int relationline(Line v){                                          //直线和圆的关系，比较的是圆心到线段的距离和半径的关系
        double dst = v.dispointtoline(p);
        if(sgn(dst-r) < 0)return 2;
        else if(sgn(dst-r) == 0)return 1;
        else return 0;
    }
    int relationcircle(circle v){                                     //两圆关系，5相离，4外切，3相交，2内切，1内含
        double d = p.distance(v.p);
        if(sgn(d-r-v.r) > 0)return 5;
        if(sgn(d-r-v.r) == 0)return 4;
        double l = fabs(r-v.r);
        if(sgn(d-r-v.r)<0 && sgn(d-l)>0)return 3;
        if(sgn(d-l) == 0)return 2;
        if(sgn(d-l) < 0)return 1;
    }
    int pointcrosscircle(circle v,Point &p1,Point &p2){               //求两圆交点，0是无交点，1是一个交点，2是两个
        int rel = relationcircle(v);
        if(rel == 1 || rel == 5)return 0;
        double d = p.distance(v.p);
        double l = (d*d+r*r-v.r*v.r)/(2*d);
        double h = sqrt(r*r-l*l);
        Point tmp = p + (v.p-p).trunc(l);
        p1 = tmp + ((v.p-p).rotleft().trunc(h));
        p2 = tmp + ((v.p-p).rotright().trunc(h));
        if(rel == 2 || rel == 4)
            return 1;
        return 2;
    }
};
struct polygon{
    int n;
    Point p[maxp];
    Line l[maxp];
    void input(int _n){
        n = _n;
        for(int i = 0; i < n; ++i) p[i].input();
    }
    void add(Point q){p[n++] = q;}
    void getline(){
        for(int i = 0; i < n; ++i){
            l[i] = Line(p[i],p[(i+1)%n]);
        }
    }
    struct cmp{
        Point p;
        cmp(const Point &p0){p = p0;}
        bool operator()(const Point &aa,const Point &bb){
            Point a = aa,b = bb;
            int d = sgn((a-p)^(b-p));
            if(d == 0) return sgn(a.distance(p)-b.distance(p))<0;
            return d > 0;
        }
    };
    void norm(){                                     //进行极角排序，首先找到最左下角的点
        Point mi = p[0];
        for(int i = 1; i < n; ++i) mi = min(mi,p[i]);
        sort(p,p+n,cmp(mi));
    }
    Point getbarycentre(){                          //得到重心
        Point ret(0,0);
        double area = 0;
        for(int i = 1; i < n-1; ++i){
            double tmp = (p[i]-p[0])^(p[i+1]-p[0]);
            if(sgn(tmp) == 0) continue;
            area += tmp;
            ret.x += (p[0].x+p[i].x+p[i+1].x)/3*tmp;
            ret.y += (p[0].y+p[i].y+p[i+1].y)/3*tmp;
        }
        if(sgn(area)) ret = ret/area;
        return ret;
    }

};