凸包问题——圈水池(nyist 78)
#include <iostream>#include <cstring>#include <algorithm>using namespace std;struct point{int x,y;};int cmp1 (point A,point B)// 按y排序 { return A.y < B.y || (A.y == B.y && A.x < B.x); } int cmp2(point A,point B)//// 按x排序 {return A.x<B.x||(A.x==B.x&&A.y<B.y); }int multi(point p0,point p1,point p2){return (p1.x-p0.x)*(p2.y-p0.y)>(p1.y-p0.y)*(p2.x-p0.x); }//此处是大于号 int graham(point pnt[], int n, point res[])//选中的点在保存在res数组中，个数是top { int i, len, k = 0, top = 1; sort(pnt, pnt + n,cmp1); if (n == 0) return 0; res[0] = pnt[0]; if (n == 1) return 1; res[1] = pnt[1]; if (n == 2) return 2; res[2] = pnt[2]; for (i = 2; i < n; i++) { while (top && multi(pnt[i], res[top], res[top-1])) top--; res[++top] = pnt[i]; } len = top; res[++top] = pnt[n - 2]; for (i = n - 3; i >= 0; i--) { while (top!=len && multi(pnt[i], res[top], res[top-1])) top--; res[++top] = pnt[i]; } return top; // 返回凸包中点的个数 }int main(void){int t,i,n;point a[105],b[105];cin>>t;while(t--){ i=0;cin>>n;while(i<n) { cin>>a[i].x>>a[i].y; i++; }n=graham(a,n,b);sort(b,b+n,cmp2);for(i=0;i<n;i++)cout<<b[i].x<<' '<<b[i].y<<endl;}}