NYOJ 圈水池

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

struct node

{

    int x,y;

};

node vex[];//存入的所有的点

node stackk[];//凸包中所有的点

int xx,yy;

bool cmp1(node a,node b)//排序找第一个点

{

    if(a.y==b.y)

        return a.x<b.x;

    else

        return a.y<b.y;

}

bool cmp(node a,node b)//排序找第一个点

{

    if(a.x==b.x)

        return a.y<b.y;

    else

        return a.x<b.x;

}

int cross(node a,node b,node c)//计算叉积

{

    return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);

}

bool cmp2(node a,node b)//极角排序另一种方法，速度快

{

    if(atan2(a.y-yy,a.x-xx)!=atan2(b.y-yy,b.x-xx))

        return (atan2(a.y-yy,a.x-xx))<(atan2(b.y-yy,b.x-xx));

    return a.x<b.x;

}

int main()

{

    int t,L,n,m;

    cin>>n;

    while(n--)

    {

        cin>>m;

        int i;

        for(i=; i<m; i++)

        {

            scanf("%d%d",&vex[i].x,&vex[i].y);

        }

        memset(stackk,,sizeof(stackk));

        sort(vex,vex+m,cmp1);

        stackk[]=vex[];

        xx=stackk[].x;

        yy=stackk[].y;

        sort(vex+,vex+m,cmp2);//cmp2是更快的，cmp更容易理解

        stackk[]=vex[];//将凸包中的第两个点存入凸包的结构体中

        int top=;//最后凸包中拥有点的个数

        for(i=; i<m; i++)

        {

            while(i>=&&cross(stackk[top-],stackk[top],vex[i])<)   //对使用极角排序的i>=1有时可以不用，但加上总是好的

                top--;

            stackk[++top]=vex[i];                                    //控制<0或<=0可以控制重点，共线的，具体视题目而定。

        }

           sort(stackk,stackk+top+,cmp);

           for(i=;i<=top;i++)

               printf("%d %d\n",stackk[i].x,stackk[i].y);

    }

}