简单几何(凸包+多边形面积) POJ 3348 Cows

题目传送门

题意:求凸包 + (int)求面积 / 50

/************************************************
* Author :Running_Time
* Created Time :2015/11/4 星期三 11:13:29
* File Name :POJ_3348.cpp
************************************************/ #include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std; #define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = acos (-1.0);
int dcmp(double x) {
if (fabs (x) < EPS) return 0;
else return x < 0 ? -1 : 1;
}
struct Point {
double x, y;
Point () {}
Point (double x, double y) : x (x), y (y) {}
Point operator - (const Point &r) const {
return Point (x - r.x, y - r.y);
}
bool operator < (const Point &r) const {
return x < r.x || (x == r.x && y < r.y);
}
bool operator == (const Point &r) const {
return dcmp (x - r.x) == 0 && dcmp (y - r.y) == 0;
}
};
typedef Point Vector;
Point read_point(void) {
double x, y; scanf ("%lf%lf", &x, &y);
return Point (x, y);
}
double dot(Point a, Point b) {
return a.x * b.x + a.y * b.y;
}
double cross(Vector A, Vector B) {
return A.x * B.y - A.y * B.x;
}
bool on_seg(Point p, Point a, Point b) {
return dcmp (cross (a - p, b - p)) == 0 && dcmp (dot (a - p, b - p)) < 0;
}
double area_poly(vector<Point> ps) {
double ret = 0;
for (int i=1; i<ps.size ()-1; ++i) {
ret += fabs (cross (ps[i] - ps[0], ps[i+1] - ps[0])) / 2;
}
return ret;
} /*
凸包边上无点:<= 凸包边上有点:<
*/
vector<Point> convex_hull(vector<Point> ps) {
sort (ps.begin (), ps.end ());
int n = ps.size (), k = 0;
vector<Point> qs (n * 2);
for (int i=0; i<n; ++i) {
while (k > 1 && cross (qs[k-1] - qs[k-2], ps[i] - qs[k-1]) <= 0) k--;
qs[k++] = ps[i];
}
for (int t=k, i=n-2; i>=0; --i) {
while (k > t && cross (qs[k-1] - qs[k-2], ps[i] - qs[k-1]) <= 0) k--;
qs[k++] = ps[i];
}
qs.resize (k - 1);
return qs;
}
int main(void) {
int n;
while (scanf ("%d", &n) == 1) {
vector<Point> ps;
for (int i=0; i<n; ++i) ps.push_back (read_point ());
vector<Point> qs = convex_hull (ps);
double area = area_poly (qs);
printf ("%d\n", (int) area / 50);
} //cout << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n"; return 0;
}

  

上一篇:「mysql优化专题」单表查询优化的一些小总结,非索引设计(3)


下一篇:数据库热备之SQLServer的数据库镜像实施笔记