#include<iostream>#include<cstdio>#include<cmath>#include<memory.h>#include<cstring>#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){};};//有公共端點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 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));}//多邊形，逆時針或順時針給出x,ystruct POLY{    int n;    double *x;//n個點    double *y;//x,y為點的指針，首尾必須重合    POLY():n(0),x(NULL),y(NULL){};    POLY(int _n,const double *_x,const double *_y)    {        n=_n;        x=new double[n+1];        memcpy(x,_x,n*sizeof(double));        x[n]=_x[0];        y=new double[n+1];        memcpy(y,_y,n*sizeof(double));        y[n]=_y[0];    }};//多邊形頂點POINT Vertex(const POLY &poly,int idx){    idx%=poly.n;    return POINT(poly.x[idx],poly.y[idx]);}//多邊形的邊SEG Edge(const POLY &poly,int idx){    idx%=poly.n;    return SEG(POINT(poly.x[idx],poly.y[idx]),               POINT(poly.x[idx+1],poly.y[idx+1]));}//多邊形的周長double Perimeter(const POLY &poly){    double p=0.0;    for(int i=0;i<poly.n;i++)        p=p+Distance(Vertex(poly,i),Vertex(poly,i+1));    return p;}double Area(const POLY &poly){    if(poly.n<3) return double(0);    double s=poly.y[0]*(poly.x[poly.n-1]-poly.x[1]);    for(int i=1;i<poly.n;i++)        s+=poly.y[i]*(poly.x[i-1]-poly.x[(i+1)%poly.n]);    return s/2;}//多邊形的重心POINT InCenter(const POLY &poly){    double S,Si,Ax,Ay;    POINT p;    Si=(poly.x[poly.n-1]*poly.y[0]-poly.x[0]*poly.y[poly.n-1]);    S=Si;    Ax=Si*(poly.x[0]+poly.x[poly.n-1]);    Ay=Si*(poly.y[0]+poly.y[poly.n-1]);    for(int i=1;i<poly.n;i++)    {        Si=(poly.x[i-1]*poly.y[i]-poly.x[i]*poly.y[i-1]);        Ax+=Si*(poly.x[i-1]+poly.x[i]);        Ay+=Si*(poly.y[i-1]+poly.y[i]);;        S+=Si;    }    S=S*3;    return POINT (Ax/S,Ay/S);}//判斷點是否在多邊形上bool IsOnPoly(const POLY &poly,const POINT &p){    for(int i=0;i<poly.n;i++)    {        if(IsOnSeg(Edge(poly,i),p))        {            return true;        }    }    return false;}//判斷點是否在多邊形內部bool IsInPoly(const POLY &poly,const POINT &p){    SEG L(p,POINT(INF,p.y));    int count=0;    for(int i=0;i<poly.n;i++)    {        SEG S=Edge(poly,i);        if(IsOnSeg(S,p))            return true;//如果在poly上則返回true        if(!IsEqual(S.a.y,S.b.y))        {            POINT &p=(S.a.y>S.b.y)?(S.a):(S.b);            if(IsOnSeg(L,p))            {                ++count;            }            else if(!IsOnSeg(L,S.a)&&!IsOnSeg(L,S.b)&&IsIntersect(S,L))            {                ++count;            }        }    }    return (count%2!=0);}//判斷是否為簡單多邊形bool IsSimple(const POLY &poly){    if(poly.n<3)        return false;    SEG L1,L2;    for(int i=0;i<poly.n-1;i++)    {        L1=Edge(poly,i);        for(int j=i+1;j<poly.n;j++)        {            L2=Edge(poly,j);            if(j==i+1)            {                if(IsOnSeg(L1,L2.b)||IsOnSeg(L2,L1.a))                    return false;            }            else if(j==poly.n-i-1)            {                if(IsOnSeg(L1,L2.a)||IsOnSeg(L2,L1.b))                    return false;            }            else            {                if(IsIntersect(L1,L2))                    return false;            }        }    }    return false;}//點陣的凸包，返回一個多邊形POLY ConvexHull(const POINT *set,int n)//不適用于點少于3個的情況{    POINT * points=new POINT[n];    memcpy(points,set,n*sizeof(POINT));    double *X=new double[n];    double *Y=new double[n];    int k=0,top=2;    for(int i=1;i<n;i++)    {        if((points[i].y<points[k].y)||          ((points[i].y==points[k].y)&&           (points[i].x<points[k].x)))        {            k=i;        }    }    swap(points[0],points[k]);    for(int i=1;i<n-1;i++)    {        k=i;        for(int j=i+1;j<n;j++)        {            if((Cross(points[j],points[k],points[0])>0)||              ((Cross(points[j],points[k],points[0])==0)&&              (Distance(points[0],points[j])<Distance(points[0],points[k]))))            {                k=j;            }        }        swap(points[i],points[k]);    }    X[0]=points[0].x;Y[0]=points[0].y;    X[1]=points[1].x;Y[1]=points[1].y;    X[2]=points[2].x;Y[2]=points[2].y;    for(int i=3;i<n;i++)    {        while(Cross(points[i],POINT(X[top],Y[top]),                    POINT(X[top-1],Y[top-1]))>=0)        {            top--;        }        top++;        X[top]=points[i].x;        Y[top]=points[i].y;    }    delete[] points;    POLY poly(++top,X,Y);    delete[] X;    delete[] Y;    return poly;}