#pragma comment(linker, "/STACK:1024000000,1024000000")#include<iostream>#include<cstdio>#include<cmath>#include<string>#include<queue>#include<algorithm>#include<stack>#include<cstring>#include<vector>#include<list>#include<set>#include<map>using namespace std;#define ll long long#define bug(x)  cout<<"bug"<<x<<endl;const int N=1e5+10,M=1e6+10,inf=2147483647;const ll INF=1e18+10,mod=2147493647;const double eps = 1e-8;const double PI = acos(-1.0);int sgn(double x){    if(fabs(x) < eps)return 0;    if(x < 0)return -1;    else return 1;}struct Point{    double x,y;    Point() {}    Point(double _x,double _y)    {        x = _x;        y = _y;    }    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;    }//绕原点旋转角度B（弧度值），后x,y的变化    void transXY(double B)    {        double tx = x,ty = y;        x= tx*cos(B) - ty*sin(B);        y= tx*sin(B) + ty*cos(B);    }};struct Line{    Point s,e;    Line() {}    Line(Point _s,Point _e)    {        s = _s;        e = _e;    }//两直线相交求交点 //第一个值为0表示直线重合，为1表示平行，为0表示相交,为2是相交 //只有第一个值为2时，交点才有意义    pair<int,Point> operator &(const Line &b)const    {        Point res = s;        if(sgn((s-e)^(b.s-b.e)) == 0)        {            if(sgn((s-b.e)^(b.s-b.e)) == 0) return make_pair(0,res);//重合            else return make_pair(1,res);//平行        }        double t = ((s-b.s)^(b.s-b.e))/((s-e)^(b.s-b.e));        res.x += (e.x-s.x)*t;        res.y += (e.y-s.y)*t;        return make_pair(2,res);    }};//*两点间距离double dist(Point a,Point b){    return sqrt((a-b)*(a-b));}// *判断线段相交bool inter(Line l1,Line l2){    return        max(l1.s.x,l1.e.x) >= min(l2.s.x,l2.e.x) &&        max(l2.s.x,l2.e.x) >= min(l1.s.x,l1.e.x) &&        max(l1.s.y,l1.e.y) >= min(l2.s.y,l2.e.y) &&        max(l2.s.y,l2.e.y) >= min(l1.s.y,l1.e.y) &&        sgn((l2.s-l1.e)^(l1.s-l1.e))*sgn((l2.e-l1.e)^(l1.s-l1.e)) <= 0 &&        sgn((l1.s-l2.e)^(l2.s-l2.e))*sgn((l1.e-l2.e)^(l2.s-l2.e)) <= 0;}//判断直线l1和线段l2是否相交bool Seg_inter_line(Line  l1,Line l2){    return sgn((l2.s-l1.e)^(l1.s-l1.e))*sgn((l2.e-l1.e)^(l1.s-l1.e)) <= 0;}//点到直线距离 //返回为result,是点到直线最近的点Point PointToLine(Point P,Line L){    Point result;    double t = ((P-L.s)*(L.e-L.s))/((L.e-L.s)*(L.e-L.s));    result.x = L.s.x + (L.e.x-L.s.x)*t;    result.y = L.s.y + (L.e.y-L.s.y)*t;    return result;}//点到线段的距离//返回点到线段最近的点Point NearestPointToLineSeg(Point P,Line L){    Point result;    double t = ((P-L.s)*(L.e-L.s))/((L.e-L.s)*(L.e-L.s));    if(t >= 0 && t <= 1)    {        result.x = L.s.x + (L.e.x - L.s.x)*t;        result.y = L.s.y + (L.e.y - L.s.y)*t;    }    else    {        if(dist(P,L.s) < dist(P,L.e)) result = L.s;        else result = L.e;    }    return result;}//计算多边形面积//点的编号从0~n-1double CalcArea(Point p[],int n){    double res = 0;    for(int i = 0; i < n; i++)        res += (p[i]^p[(i+1)%n])/2;    return fabs(res);}//*判断点在线段上bool OnSeg(Point P,Line L){    return        sgn((L.s-P)^(L.e-P)) == 0 &&        sgn((P.x - L.s.x) * (P.x - L.e.x)) <= 0 && sgn((P.y - L.s.y) * (P.y - L.e.y)) <= 0;}//*判断点在凸多边形内//点形成一个凸包，而且按逆时针排序（如果是顺时针把里面的<0改为>0） //点的编号:0~n-1//返回值：//-1:点在凸多边形外//0:点在凸多边形边界上//1:点在凸多边形内int inConvexPoly(Point a,Point p[],int n){    for(int i = 0; i < n; i++)    {        if(sgn((p[i]-a)^(p[(i+1)%n]-a)) < 0)return -1;        else if(OnSeg(a,Line(p[i],p[(i+1)%n])))return 0;    }    return 1;}//*判断点在任意多边形内//射线法，poly[]的顶点数要大于等于3,点的编号0~n-1 //返回值//-1:点在凸多边形外//0:点在凸多边形边界上//1:点在凸多边形内int inPoly(Point p,Point poly[],int n){    int cnt;    Line ray,side;    cnt = 0;    ray.s = p;    ray.e.y = p.y;    ray.e.x = -100000000000.0;//-INF,注意取值防止越界    for(int i = 0; i < n; i++)    {        side.s = poly[i];        side.e = poly[(i+1)%n];        if(OnSeg(p,side))return 0;//如果平行轴则不考虑        if(sgn(side.s.y - side.e.y) == 0)            continue;        if(OnSeg(side.s,ray))        {            if(sgn(side.s.y - side.e.y) > 0)cnt++;        }        else if(OnSeg(side.e,ray))        {            if(sgn(side.e.y - side.s.y) > 0)cnt++;        }        else if(inter(ray,side))            cnt++;    }    if(cnt % 2 == 1)return 1;    else return -1;}//判断凸多边形 //允许共线边//点可以是顺时针给出也可以是逆时针给出//点的编号1~n-1bool isconvex(Point poly[],int n){    bool s[3];    memset(s,false,sizeof(s));    for(int i = 0; i < n; i++)    {        s[sgn( (poly[(i+1)%n]-poly[i])^(poly[(i+2)%n]-poly[i]) )+1] = true;        if(s[0] && s[2])return false;    }    return true;}/*0求凸包，Graham算法0点的编号0~n-10返回凸包结果Stack[0~top-1]为凸包的编号 */const int MAXN = 1010;Point listt[MAXN];int Stack[MAXN],top; //相对于listt[0]的极角排序bool _cmp(Point p1,Point p2){    double tmp = (p1-listt[0])^(p2-listt[0]);    if(sgn(tmp) > 0)return true;    else if(sgn(tmp) == 0 && sgn(dist(p1,listt[0]) - dist(p2,listt[0])) <= 0) return true;    else return false;}void Graham(int n){    Point p0;    int k = 0;    p0 = listt[0]; //找最下边的一个点    for(int i = 1; i < n; i++)    {        if( (p0.y > listt[i].y) || (p0.y == listt[i].y && p0.x > listt[i].x) )        {            p0 = listt[i];            k = i;        }    }    swap(listt[k],listt[0]);    sort(listt+1,listt+n,_cmp);    if(n == 1)    {        top = 1;        Stack[0] = 0;        return;    }    if(n == 2)    {        top = 2;        Stack[0] = 0;        Stack[1] = 1;        return ;    }    Stack[0] = 0;    Stack[1] = 1;    top = 2;    for(int i = 2; i < n; i++)    {        while(top > 1 && sgn((listt[Stack[top-1]]-listt[Stack[top-2]])^(listt[i]-listt[Stack[top-2]])) <= 0)            top--;        Stack[top++] = i;    }}int main(){    return 0;}