POJ 3348 Cows 凸包 + 多边形面积公式

发布时间:2017-3-25 17:42:19 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"POJ 3348 Cows 凸包 + 多边形面积公式",主要涉及到POJ 3348 Cows 凸包 + 多边形面积公式方面的内容,对于POJ 3348 Cows 凸包 + 多边形面积公式感兴趣的同学可以参考一下。

一定要注意 总的点数 n<= 2 时 graham不适用。 还要注意 graham找到凸包后 注意 top <=2 时面积为0。 View Code #include<stdio.h> #include<string.h> #include<math.h> #include<algorithm> using namespace std; struct point { double x, y; }p[10003]; double det(double x1, double y1, double x2, double y2) { return x1 * y2 - x2 * y1; } double cross(point o, point a, point b) { return det(a.x - o.x, a.y - o.y, b.x - o.x, b.y - o.y); } bool cmp(point a, point b) { if(a.y == b.y) return a.x < b.x; return a.y < b.y; } int n; int top; point res[10003<<1]; void graham() { sort(p, p + n, cmp); int i; top = -1; if(n <= 2 ) return; res[++top] = p[0]; res[++top] = p[1]; for(i = 2; i < n; i++) { while(top >= 1 && cross(res[top-1], res[top], p[i]) <= 0 ) top--; res[++top] = p[i]; } res[++top] = p[n-2]; int t = top; for(i = n - 3; i >= 0; i--) { while(top >= t && cross(res[top-1], res[top], p[i]) <= 0) top--; res[++top] = p[i]; } } double cal_area(int n, point* p){ double s = 0; int i; p[n] = p[0]; for (i = 0; i < n; i++) s += p[i].x * p[i+1].y - p[i].y * p[i+1].x; return fabs(s)/2; } int main() { int i, j; while( ~scanf("%d", &n) ) { for(i = 0; i < n; i++) scanf("%lf%lf", &p[i].x, &p[i].y); graham(); if(top <= 2) { printf("0\n"); continue; } double ans = cal_area(top, res); printf("%d\n", (int) (ans/50)); } return 0; }

上一篇:《android 4高级编程》--android简介
下一篇:POJ 1654 Area 多边形面积

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款