首页 > 代码库 > POJ 3348 - Cows 凸包面积
POJ 3348 - Cows 凸包面积
求凸包面积。求结果后不用加绝对值,这是BBS()排序决定的。
//Ps 熟练了template <class T>之后用起来真心方便= =
//POJ 3348 //凸包面积 //1A 2016-10-15 #include <cstdio> #include <cstdlib> #include <cmath> #include <iostream> #include <cstring> #define MAXN (10000 + 10) struct point{ int x, y; point(){} point(int X, int Y): x(X), y(Y){} friend int operator ^ (const point &p1, const point &p2){ return p1.x * p2.y - p1.y * p2.x; } friend point operator >> (const point &p1, const point &p2){ return point(p2.x - p1.x, p2.y - p1.y); } friend bool operator < (const point &p1, const point &p2){ return (p1.x < p2.x)||(p1.x == p2.x)&&(p1.y < p2.y); } }pt[MAXN]; template <class T> void swap(T &a, T & b){ T t = a; a = b; b = t; } template <class T> void BBS(T a[], int n){ for (int i = 0; i < n; i++) for (int j = 0; j < i; j++) if (a[i] < a[j]) swap(a[j], a[i]); } double convex_hull(point p[], int n){ int cur = 0; double area = 0; BBS(p, n); while (1){ int tmp = - 1; for (int i = 0; i < n; i++){ if (cur != i){ if (!(tmp + 1)||((p[cur] >> p[i]) ^ (p[cur] >> p[tmp])) > 0) tmp = i; } } if (tmp + 1){ area += p[cur] ^ p[tmp]; } if (!tmp||!(tmp + 1)) return area / 2; cur = tmp; } } int main(){ int n; freopen("fin.c", "r", stdin); scanf("%d", &n); for (int i = 0; i < n; i++){ scanf("%d%d", &pt[i].x, &pt[i].y); } printf("%d\n", int(convex_hull(pt, n)/50)); }
POJ 3348 - Cows 凸包面积
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。