首页 > 代码库 > 【poj3348】 Cows
【poj3348】 Cows
http://poj.org/problem?id=3348 (题目链接)
题意:给出平面上n个点,以这n个点中的一些围成的多边形面积 div 50的最大值。
Solution
凸包求面积。
很好做,构造完凸包后从栈底开始向上求叉乘之和,也就是将凸包分成许多小三角形求面积和。
代码:
// poj3348#include<algorithm>#include<iostream>#include<cstring>#include<cstdlib>#include<cstdio>#include<cmath>#include<map>#define inf 2147483640#define LL long long#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout);using namespace std;inline LL getint() { LL x=0,f=1;char ch=getchar(); while (ch>‘9‘ || ch<‘0‘) {if (ch==‘-‘) f=-1;ch=getchar();} while (ch>=‘0‘ && ch<=‘9‘) {x=x*10+ch-‘0‘;ch=getchar();} return x*f;}const int maxn=10010;struct point {int x,y;}p[maxn];int s[maxn],n,top;int cross(point p0,point a,point b) { return (a.x-p0.x)*(b.y-p0.y)-(a.y-p0.y)*(b.x-p0.x);}double dis(point a,point b) { return sqrt((double)(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}bool cmp(point a,point b) { int t=cross(p[1],a,b); if (t>0) return 1; else if (t==1 && dis(a,p[1])<dis(b,p[1])) return 1; else return 0;}void Graham() { if (n==1) s[top=1]=1; else if (n==2) {s[top=1]=1;s[++top]=2;} else { s[top=1]=1;s[++top]=2; for (int i=3;i<=n;i++) { while (top>1 && cross(p[s[top-1]],p[s[top]],p[i])<=0) top--; s[++top]=i; } }}double Size() { point p0=p[s[1]]; double sum=0; for (int i=3;i<=top;i++) sum+=cross(p0,p[s[i-1]],p[s[i]]); return sum/2;}int main() { while (scanf("%d",&n)!=EOF) { int k=1; for (int i=1;i<=n;i++) { scanf("%d%d",&p[i].x,&p[i].y); if (p[i].x<p[k].x || (p[i].x==p[k].x && p[i].y<p[k].y)) k=i; } point p0=p[k]; p[k]=p[1];p[1]=p0; sort(p+2,p+1+n,cmp); Graham(); printf("%d\n",(int)Size()/50); } return 0;}
【poj3348】 Cows
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。