首页 > 代码库 > 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;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。