凸包 模版
//计算凸包，输入点数组p,个数为p，输出点数组为ch。函数返回凸包顶点数
//输入不能有重复节点
//如果精度要求搞需要用dcmp判断
//如果不希望在边上右点，需要将 <= 改为 <
int ConvexHull(Point *p,int n ,Point *ch)
{
sort(p,p+n);
int m = 0;
for(int i = 0;i < n; ++i)
{
while(m>1&& Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
ch[m++] = p[i];
}
int k = m;
for(int i = n-2; i >= 0; --i)
{
while(m > k&& Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2]) <= 0) m--;
ch[m++] = p[i];
}
if(n > 1) m--;
return m;
}
查看8道真题和解析
