首页 > 代码库 > POJ 2079

POJ 2079

2024-07-15 18:54:28   213人阅读

呃，不知道我用的算不算卡壳，总有点枚举的意思。

先求凸包，然后，枚举其中一点，再枚举另一点作为结尾，这个向量旋转一周后，求出最大值面积。这里面用的是旋转卡壳判断的那个式子。

#include <iostream>#include <cstdio>#include <algorithm>#include <cmath>using namespace std;struct point{	int x,y;}p[50050];int n;int ans[50050],st[50050],cnt,stop;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;}int multi(point a,point b,point c){	point p1; p1.x=a.x-c.x; p1.y=a.y-c.y;	point p2; p2.x=b.x-c.x; p2.y=b.y-c.y;	return p1.x*p2.y-p1.y*p2.x;}void slove(){	cnt=stop=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]])>0) 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]])>0) stop--;		st[stop++]=i;	}	for(int i=1;i<stop;i++)	ans[cnt++]=st[i];}double Triangle(point a,point b,point c){	point p1; p1.x=a.x-c.x; p1.y=a.y-c.y;	point p2; p2.x=b.x-c.x; p2.y=b.y-c.y;	return fabs((p1.x*p2.y-p1.y*p2.x)*1.0)/2.0;}double Area(){	int q;	double anst=0;	for(int i=0;i<cnt;i++){		q=i+1;		for(int j=i+1;j<cnt;j++){		while(Triangle(p[ans[i]],p[ans[j]],p[ans[q]])<Triangle(p[ans[i]],p[ans[j]],p[ans[(q+1)%cnt]]))		q=(q+1)%cnt;		anst=max(anst,Triangle(p[ans[i]],p[ans[j]],p[ans[q]]));		}	}	return anst;}int main(){	while(scanf("%d",&n)!=EOF){		if(n==-1) break;		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;		anst=max(anst,Area());		printf("%.2lf\n",anst);	}	return 0;}

　　


联系
我们