Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 4300 Accepted: 1849
Description
The art galleries of the new and very futuristic building of the Center for Balkan Cooperation have the form of polygons (not necessarily convex). When a big exhibition is organized, watching over all of the pictures is a big security concern. Your task is that for a given gallery to write a program which finds the surface of the area of the floor, from which each point on the walls of the gallery is visible. On the figure 1. a map of a gallery is given in some co-ordinate system. The area wanted is shaded on the figure 2.
Input
The number of tasks T that your program have to solve will be on the first row of the input file. Input data for each task start with an integer N, 5 <= N <= 1500. Each of the next N rows of the input will contain the co-ordinates of a vertex of the polygon ? two integers that fit in 16-bit integer type, separated by a single space. Following the row with the co-ordinates of the last vertex for the task comes the line with the number of vertices for the next test and so on.
Output
For each test you must write on one line the required surface - a number with exactly two digits after the decimal point (the number should be rounded to the second digit after the decimal point).
Sample Input
1
7
0 0
4 4
4 7
9 7
13 -1
8 -6
4 -4Sample Output
80.00
思考：求多邊形的核，給出的多邊形點的順序可能是逆序也可能是順序，給出的最大數的范圍16-bit integer type。用C++提交AC，用G++提交WA。有時間學習一下兩則的不同。
半平面問題的第一題，很興奮！
[cpp]
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <complex>
using namespace std;
const int maxn = 2000;
const double inf = 1e5;
const double eps = 1e-10;
//1279 Accepted 348K
0MS C++ 3482B 2013-06-04 09:13:50
struct point { double x;
double y;
point(){} point( double a, double b):x(a), y(b){}
friend point operator - (const point &a, const point &b) {
return point(a.x-b.x, a.y-b.y);
} };
double det(const point &a, const point &b) {
return a.x*b.y - a.y*b.x; }
struct polygon { int n;
point a[maxn]; }; //把直線化為一般式。
struct halfPlane { double a, b, c;
halfPlane(point p, point q) { a = q.y - p.y;
b = p.x - q.x; c = det(q, p); } };
struct polygon_convex { vector <point> P; };
double calc(halfPlane &L, point &a) {
return a.x*L.a + a.y*L.b + L.c; }
point Intersect(point &a, point &b, halfPlane &L) {
point res;
double t1 = calc(L, a), t2 = calc(L, b);
res.x = (t2*a.x - t1*b.x)/(t2-t1);
res.y = (t2*a.y - t1*b.y)/(t2-t1);
return res; } //將一個凸多邊形和一個半平面交。
polygon_convex cut(polygon_convex &a, halfPlane &L) {
int n = a.P.size(); polygon_convex res;
for(int i = 0; i < n; i++) {
if(calc(L, a.P[i])<-eps) {
res.P.push_back(a.P[i]); }
else { int j;
j = i - 1;
if(j < 0) j = n-1;
if(calc(L, a.P[j])<-eps)
res.P.push_back(Intersect(a.P[j], a.P[i],L));
j = i + 1;
if(j==n) j = 0;
if(calc(L, a.P[j])<-eps)
res.P.push_back(Intersect(a.P[i], a.P[j], L));
} } return res; } //參數為一個多邊形， 返回一個凸多邊形。
polygon_convex core(polygon &a) { polygon_convex res;
res.P.clear();
//清空容器. res.P.push_back(point(-inf, -inf));
res.P.push_back(point(inf, -inf));
res.P.push_back(point(inf, inf));
res.P.push_back(point(-inf, inf));
int n = a.n;
if(n==2) { halfPlane L(a.a[0], a.a[1]);
return res = cut(res, L);
}
for(int i = 0; i < n ; i++) {
halfPlane L(a.a[i], a.a[(i+1)%n]);//多邊形循環產生n個半平面。
// printf("%.2lf, %.2lf, %.2lf\n", L.a, L.b, L.c);
res = cut(res, L);//用產生的半平面調用cut去一次次切割。
} return res;//還回凸多邊形. }
//如果多邊形是順時針給出，則改變方向.
polygon init(polygon v) { int n = v.n;
double area = 0;
for(int i = 1; i < n-1; i++) {
area += det(v.a[i]-v.a[0], v.a[i+1]-v.a[0]);
} if(area < 0) { polygon temp;
temp.n = n; temp.a[0] = v.a[0];
for(int i = n-1; i >= 1; i--) {
temp.a[n-i] = v.a[i]; }
return temp; } return v; }
double get_area(polygon_convex v) {
double area = 0; int n = v.P.size();
for(int i = 1; i < n-1; i++) {
area += det(v.P[i]-v.P[0], v.P[i+1]-v.P[0]);
} return area/2; } int main() {
polygon v; point tmp;
int T;
int n; scanf("%d", &T);
while(T--) { scanf("%d", &n);
v.n = 0; for(int i = 0; i < n; i++) {
scanf("%lf%lf", &tmp.x, &tmp.y);
v.a[i] = tmp; v.n++; //別忘了。
} v = init(v);
polygon_convex ans = core(v);
double result = get_area(ans);
printf("%.2lf\n", result); } return 0; }
