凸包（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;
}