凸包（andrew）

将所有点按照x为first，y为second从小到大排序，（可以先删除相同点）得到p数组，将p1p2放到凸包中，从p3开始为左则加入，为右则删到为左，最后到最右边的点，求得下凸包，再反向一个上凸包。
//输入点数组p，个数为n，输出点数组res,函数返回凸包顶点数
//输入时先去除重复点（有需要时不去）
//若是不希望边上有两个以上的点（输入点），则将<=改为<
//精度要求高时用dcmp比较

int andrew()
{
    sort(p,p+n);
    int m=0;
    for (int i=0;i<n;i++)
    {
        while (m>1&&cross(res[m-1]-res[m-2],p[i]-res[m-2])<0) --m;
        res[m++]=p[i];
    }
    int k=m;
    for (int i=n-2;i>=0;--i)
    {
        while (m>k&&cross(res[m-1]-res[m-2],p[i]-res[m-2])<0) --m;
        res[m++]=p[i];
    }
    if (m>1) --m;
    return m;
}