poj 3787 Convex Hull of Lattice Points 求凸包

题意：

裸的凸包。

分析：

graham模板直接上。

代码：

//poj 3787
//sep9
#include <iostream>
#include <algorithm>
using namespace std;
const int maxN=64;struct P
{int x,y;	
}pnt[maxN],cnt[maxN];
int n;int cmp(P a,P b)
{if(a.y!=b.y)return a.y<b.y;return a.x<b.x;
}int cross(P a,P b,P c)
{int x1=b.x-a.x;int y1=b.y-a.y;int x2=c.x-a.x;int y2=c.y-a.y;return x1*y2-x2*y1;
}
int graham()
{sort(pnt,pnt+n,cmp);int i,pos=1;cnt[0]=pnt[0];cnt[1]=pnt[1];for(i=2;i<n;++i){while(pos>0&&cross(cnt[pos-1],cnt[pos],pnt[i])<=0) --pos;cnt[++pos]=pnt[i];		}int bak=pos;for(i=n-2;i>=0;--i){while(pos>bak&&cross(cnt[pos-1],cnt[pos],pnt[i])<=0) --pos;cnt[++pos]=pnt[i];}			return pos;
}int main()
{int cases,case_num;scanf("%d",&cases);while(cases--){scanf("%d%d",&case_num,&n);	int pos;for(int i=0;i<n;++i)scanf("%d%d",&pnt[i].x,&pnt[i].y);printf("%d %d\n",case_num,pos=graham());		int index=0;for(int i=1;i<pos;++i)if(cnt[i].y>cnt[index].y)index=i;else if(cnt[i].y==cnt[index].y&&cnt[i].x<cnt[index].x)index=i;int mod=pos;while(pos--){printf("%d %d\n",cnt[index].x,cnt[index].y);--index;index+=mod;index%=mod;	}}return 0;	
}