「POJ1279」Art Gallery

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 11. a map of a gallery is given in some co-ordinate system. The area wanted is shaded on the figure 22.

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 NN, 5N15005 \leq N \leq 1500. Each of the next NN rows of the input will contain the co-ordinates of a vertex of the polygon ? two integers that fit in 1616-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
2
3
4
5
6
7
8
9
1
7
0 0
4 4
4 7
9 7
13 -1
8 -6
4 -4

Sample Output

1
80.00

简要题意

让你求一个多边形的半平面交,点按照顺序给出。

Solution

赤裸裸的板子啊~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<queue>
#include<bitset>
#include<cmath>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
struct Pt {
double x,y;
Pt() {}
Pt(double _x, double _y){x = _x, y = _y;}
Pt operator *(double k) {return Pt(k * x, k * y);}
Pt operator /(double k) {return Pt(x / k, y / k);}
};
typedef Pt Vec;
Vec operator +(Vec _x, Vec _y) {return Vec(_x.x + _y.x, _x.y + _y.y);}
Vec operator -(Vec _x, Vec _y) {return Vec(_x.x - _y.x, _x.y - _y.y);}
double dot(Vec x, Vec y) {return x.x * y.x + x.y * y.y;}
double cross(Vec x, Vec y) {return x.x * y.y - x.y * y.x;}
struct Line {
Vec fi, se;
Line() {}
Line(Vec _a, Vec _b) {fi = _a, se = _b;}
};
#define eps 1e-8
Pt getins(Line a, Line b) {
double s1 = cross(b.fi - a.fi, b.se - a.fi);
double s2 = cross(b.se - a.se, b.fi - a.se);
return a.fi + (a.se - a.fi) * s1 / (s1 + s2);
}
Pt intersect(const Line &a, const Line &b)
{
double s1 = cross(b.fi - a.fi, b.se - a.fi);
double s2 = cross(b.se - a.se, b.fi - a.se);
return a.fi + (a.se - a.fi) * s1 / (s1 + s2);
}
const int N = 2100;
int n;
Pt a[N];
Line b[N];
int tot;
bool judge() {
double s = 0;
for(int i = 0; i < n; ++i)
s += cross(a[i] - a[0] ,a[(i + 1) % n] - a[0]);
return s >= eps;
}
double getAtan(Line a) {
return atan2(a.se.y- a.fi.y, a.se.x- a.fi.x);
}
bool cmp(Line a, Line b) {
double v1 = getAtan(a);
double v2 = getAtan(b);
if(fabs(v1 - v2) < eps) return cross(a.se - a.fi, b.fi - a.fi) < -eps;
return v1 < v2;
}

bool onR(Line a, Line b, Line c) {
Pt t = getins(b, c);
double s = cross(a.se - a.fi, t - a.fi);
return s < -eps;
}
int q[N], h, t;
Pt d[N];
double solve() {
sort(b, b + tot, cmp);
int c = 0;
for(int i = 0; i < tot; ++i) {
if(i == 0 || fabs(getAtan(b[i]) - getAtan(b[i - 1])) > eps) b[c++] = b[i];
}
tot = c;
h = 1, t = 0;
for(int i = 0; i < tot; ++i) {
while(h< t && onR(b[i], b[q[t - 1]], b[q[t]])) --t;
while(h< t && onR(b[i], b[q[h]], b[q[h + 1]])) ++h;
q[++t] = i;
}
while(h< t && onR(b[q[h]], b[q[t - 1]], b[q[t]])) --t;
while(h < t && onR(b[q[t]], b[q[h]], b[q[h + 1]]))++h;
double ans = 0;
c = 0;
for(int i = h; i < t; ++i) {
d[c++] = getins(b[q[i]], b[q[i + 1]]);
}
d[c++] = getins(b[q[t]], b[q[h]]);
for(int i = 0; i < c; ++i)
ans += fabs(cross(d[i] - d[0], d[(i + 1) % c] - d[0]) / 2);
return ans;
}


int main() {
int T = read();
while(T--) {
n = read();
for(int i = 0; i < n; ++i) scanf("%lf%lf",&a[i].x,&a[i].y);
tot = 0;
if(judge()) {
for(int i = 1; i <= n; ++i)
b[tot++] = Line(a[i - 1], a[i % n]);
} else {
for(int i = n; i; --i) b[tot++] = Line(a[i%n],a[i - 1]);
}
printf("%.2lf\n", solve() + eps);
}
return 0;
}