首页 > 代码库 > POJ 2007

POJ 2007

直接求凸包,输出即可。

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;const int MAXN=100;int n,l;int st[MAXN],stop,cnt;int ans[MAXN];struct point{	int x,y;}p[MAXN];bool cmp(point A,point B){	if(A.y<B.y) return true;	else if(A.y==B.y){		if(A.x<B.x) return true;	}	return false;}bool multi(point a,point b,point c){	return (a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x)<=0;}void slove(){	stop=0; cnt=0;	st[stop++]=0; st[stop++]=1;	for(int i=2;i<n;i++){		while(stop>1&&multi(p[st[stop-1]],p[i],p[st[stop-2]])) stop--;		st[stop++]=i;	}	for(int i=0;i<stop;i++){		ans[cnt++]=st[i];	}	stop=0;	st[stop++]=n-1; st[stop++]=n-2;	for(int i=n-3;i>=0;i--){		while(stop>1&&multi(p[st[stop-1]],p[i],p[st[stop-2]])) stop--;		st[stop++]=i;	}	for(int i=1;i<stop-1;i++)	ans[cnt++]=st[i];}int main(){	n=0;	while(scanf("%d%d",&p[n].x,&p[n].y)!=EOF) n++;	sort(p,p+n,cmp);	slove();	int i,k;	for(k=0;k<cnt;k++){		if(p[ans[k]].x==0&&p[ans[k]].y==0) break;	}	printf("(%d,%d)\n",p[ans[k]].x,p[ans[k]].y);	for(int i=k+1;i<cnt;i++){		printf("(%d,%d)\n",p[ans[i]].x,p[ans[i]].y);	}	for(int i=0;i<k;i++){		printf("(%d,%d)\n",p[ans[i]].x,p[ans[i]].y);	}	return 0;}