首页 > 代码库 > POJ 3348

POJ 3348

水题。不过,题意。。呵呵了。。

围一个凸包,求出面积,然后除以50就可以了。

#include <iostream>#include <cstdio>#include <algorithm>#include <cmath>using namespace std;const int MAXN=10500;struct point {	int x,y;}p[MAXN];int n;int ans[MAXN],st[MAXN];int stop,cnt;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=cnt=0;	st[stop++]=0; st[stop++]=1;	for(int i=2;i<n;i++){		while(stop>1&&multi(p[i],p[st[stop-1]],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[i],p[st[stop-1]],p[st[stop-2]])) stop--;		st[stop++]=i;	}	for(int i=1;i<stop;i++){		ans[cnt++]=st[i];	}}int cross(point a,point b,point c){	return (a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x);}int main(){	while(scanf("%d",&n)!=EOF){		for(int i=0;i<n;i++)		scanf("%d%d",&p[i].x,&p[i].y);		sort(p,p+n,cmp);		slove();		double anst=0;	//	cout<<cnt<<endl;		for(int i=1;i<cnt-2;i++){			anst+=cross(p[ans[i]],p[ans[i+1]],p[ans[0]]);		}		anst=fabs(anst)/2;	//	cout<<anst<<endl;		printf("%d\n",int(anst/50));	}	return 0;}