//大白p263   
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
using namespace std;  
const double eps=1e-8;//精度   
const int INF=1<<29;  
const double PI=acos(-1.0);  
int dcmp(double x){//判断double等于0或。。。   
    if(fabs(x) Polygon;  
Vector operator+(Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y);}//向量+向量=向量   
Vector operator-(Point a,Point b){return Vector(a.x-b.x,a.y-b.y);}//点-点=向量   
Vector operator*(Vector a,double p){return Vector(a.x*p,a.y*p);}//向量*实数=向量   
Vector operator/(Vector a,double p){return Vector(a.x/p,a.y/p);}//向量/实数=向量   
bool operator<( const Point& A,const Point& B ){return dcmp(A.x-B.x)<0||(dcmp(A.x-B.x)==0&&dcmp(A.y-B.y)<0);}  
bool operator==(const Point&a,const Point&b){return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0;}  
bool operator!=(const Point&a,const Point&b){return a==b false:true;}  
struct Segment{  
    Point a,b;  
    Segment(){}  
    Segment(Point _a,Point _b){a=_a,b=_b;}  
    bool friend operator<(const Segment& p,const Segment& q){return p.a0) return tempa-tempb;  
    else return tempa-tempb+2*PI;  
}  
double torad(double deg){return deg/180*PI;}//角度化为弧度   
Vector Rotate(Vector a,double rad){//向量逆时针旋转rad弧度   
    return Vector(a.x*cos(rad)-a.y*sin(rad),a.x*sin(rad)+a.y*cos(rad));  
}  
Vector Normal(Vector a){//计算单位法线   
    double L=Length(a);  
    return Vector(-a.y/L,a.x/L);  
}  
Point GetLineProjection(Point p,Point a,Point b){//点在直线上的投影   
    Vector v=b-a;  
    return a+v*(Dot(v,p-a)/Dot(v,v));  
}  
Point GetLineIntersection(Point p,Vector v,Point q,Vector w){//求直线交点 有唯一交点时可用   
    Vector u=p-q;  
    double t=Cross(w,u)/Cross(v,w);  
    return p+v*t;  
}  
int ConvexHull(Point* p,int n,Point* sol){//计算凸包   
    sort(p,p+n);  
    int m=0;  
    for(int i=0;i1&&Cross(sol[m-1]-sol[m-2],p[i]-sol[m-2])<=0) m--;  
        sol[m++]=p[i];  
    }  
    int k=m;  
    for(int i=n-2;i>=0;i--){  
        while(m>k&&Cross(sol[m-1]-sol[m-2],p[i]-sol[m-2])<=0) m--;  
        sol[m++]=p[i];  
    }  
    if(n>0) m--;  
    return m;  
}  
double Heron(double a,double b,double c){//海伦公式   
    double p=(a+b+c)/2;  
    return sqrt(p*(p-a)*(p-b)*(p-c));  
}  
bool SegmentProperIntersection(Point a1,Point a2,Point b1,Point b2){//线段规范相交判定   
    double c1=Cross(a2-a1,b1-a1),c2=Cross(a2-a1,b2-a1);  
    double c3=Cross(b2-b1,a1-b1),c4=Cross(b2-b1,a2-b1);  
    return dcmp(c1)*dcmp(c2)<0&&dcmp(c3)*dcmp(c4)<0;  
}  
double CutConvex(const int n,Point* poly, const Point a,const Point b, vector result[3]){//有向直线a b 切割凸多边形   
    vector points;  
    Point p;  
    Point p1=a,p2=b;  
    int cur,pre;   
    result[0].clear();   
    result[1].clear();   
    result[2].clear();  
    if(n==0) return 0;  
    double tempcross;  
    tempcross=Cross(p2-p1,poly[0]-p1);  
    if(dcmp(tempcross)==0) pre=cur=2;  
    else if(tempcross>0) pre=cur=0;  
    else pre=cur=1;  
    for(int i=0;i0) cur=0;  
        else cur=1;  
        if(cur==pre){  
            result[cur].push_back(poly[(i+1)%n]);   
        }  
        else{  
            p1=poly[i];   
            p2=poly[(i+1)%n];  
            p=GetLineIntersection(p1,p2-p1,a,b-a);  
            points.push_back(p);   
            result[pre].push_back(p);   
            result[cur].push_back(p);   
            result[cur].push_back(poly[(i+1)%n]);   
            pre=cur;  
        }  
    }  
    sort(points.begin(),points.end());  
    if(points.size()<2){  
        return 0;   
    }  
    else{  
        return Length(points.front()-points.back());  
    }  
}  
double DistanceToSegment(Point p,Segment s){//点到线段的距离   
    if(s.a==s.b) return Length(p-s.a);  
    Vector v1=s.b-s.a,v2=p-s.a,v3=p-s.b;  
    if(dcmp(Dot(v1,v2))<0) return Length(v2);  
    else if(dcmp(Dot(v1,v3))>0) return Length(v3);  
    else return fabs(Cross(v1,v2))/Length(v1);  
}  
bool isPointOnSegment(Point p,Segment s){  
    return dcmp(Cross(s.a-p,s.b-p))==0&&dcmp(Dot(s.a-p,s.b-p))<0;  
}  
int isPointInPolygon(Point p, Point* poly,int n){//点与多边形的位置关系   
    int wn=0;  
    for(int i=0;i0&&d1<=0&&d2>0)wn++;  
        if(k<0&&d2<=0&&d1>0)wn--;  
    }  
    if(wn) return 1;//点在内部   
    else return 0;//点在外部   
}  
double PolygonArea(Point* p,int n){//多边形有向面积   
    double area=0;  
    for(int i=1;iCross(ch[q]-ch[p+1],ch[p]-ch[p+1]))  
            q=(q+1)%n;  
        ans=max(ans,max(Length(ch[p]-ch[q]),Length(ch[p+1]-ch[q+1])));  
    }  
    return ans;  
}  
Polygon CutPolygon(Polygon poly,Point a,Point b){//用a->b切割多边形 返回左侧   
    Polygon newpoly;  
    int n=poly.size();  
    for(int i=0;i=0) newpoly.push_back(c);  
        if(dcmp(Cross(b-a,c-d))!=0){  
            Point ip=GetLineIntersection(a,b-a,c,d-c);  
            if(isPointOnSegment(ip,Segment(c,d))) newpoly.push_back(ip);  
        }  
    }  
    return newpoly;  
}  
int GetCircleCircleIntersection