首页 > 代码库 > POJ 2079
POJ 2079
呃,不知道我用的算不算卡壳,总有点枚举的意思。
先求凸包,然后,枚举其中一点,再枚举另一点作为结尾,这个向量旋转一周后,求出最大值面积。这里面用的是旋转卡壳判断的那个式子。
#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;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。