「BZOJ2618」[CQOI2006]凸多边形

Description

逆时针给出nn个凸多边形的顶点坐标,求它们交的面积。例如n=2n=2时,两个凸多边形如下图:

则相交部分的面积为5.2335.233

Input

第一行有一个整数nn,表示凸多边形的个数,以下依次描述各个多边形。第ii个多边形的第一行包含一个整数mim_i,表示多边形的边数,以下mim_i行每行两个整数,逆时针给出各个顶点的坐标。

Output

输出文件仅包含一个实数,表示相交部分的面积,保留三位小数。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
2
6
-2 0
-1 -2
1 -2
2 0
1 2
-1 2
4
0 -3
1 -1
2 2
-1 0

Sample Output

1
5.233

HINT

100%100\%的数据满足:2n102\leq n\leq 103mi503\leq m_i\leq 50,每维坐标为[1000,1000][-1000,1000]内的整数

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
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#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("");}
typedef struct Vec {
double x, y;
Vec(){}
Vec(double _x, double _y) {x = _x, y = _y;}
Vec operator *(double k) {return Vec(x * k, y * k);}
Vec operator /(double k) {return Vec(x / k, y / k);}
}Pt;
Vec operator +(Vec a, Vec b) {return Vec(a.x + b.x, a.y+ b.y);}
Vec operator -(Vec a, Vec b) {return Vec(a.x - b.x, a.y- b.y);}
double dot(Vec a, Vec b) {return a.x * b.x + a.y * b.y;}
double cross(Vec a, Vec b) {return a.x * b.y - a.y * b.x;}
struct Line {
Pt s, e;
Line(){}
Line(Pt _s, Pt _e) {s = _s, e = _e;}
};
const int N = 510;
Pt a[N], d[N];
Line b[N];
int n;
Pt getins(Line a, Line b) {
double s1 = cross(b.e - a.s, b.s - a.s);
double s2 = cross(b.s - a.e, b.e - a.e);
return a.s + (a.e - a.s) * s1 / (s1 + s2);
}
double getAtan(Line a) {
return atan2(a.e.y - a.s.y, a.e.x - a.s.x);
}
#define eps 1e-9
bool cmp(Line a, Line b) {
double v1 = getAtan(a);
double v2 = getAtan(b);
if(fabs(v1 - v2) < eps) return cross(a.e - a.s, b.s - a.s) < -eps;
return v1 - v2 < -eps;
}
bool onR(Line a, Line b, Line c) {
Pt t = getins(b, c);
return cross(a.e- a.s, t - a.s) < -eps;
}
int q[N];
double solve() {
sort(b,b+n,cmp);
int c = 0;
for(int i = 0; i < n; ++i) if(!i || fabs(getAtan(b[i]) - getAtan(b[i - 1])) > eps)
b[c++] = b[i];
int h = 1, t = 0;
for(int i = 0; i < c; ++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;
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]]);
double ans = 0;
for(int i = 0; i < c; ++i)
ans += cross(d[i] - d[0], d[(i + 1) % c] - d[0]);
return ans/2;
}
int main() {
int T = read();
while(T--) {
int m = read();
for(int i = 0; i < m; ++i) {
a[i].x = read(), a[i].y = read();
}
for(int i = 0; i < m; ++i)
b[n++] = Line(a[i], a[(i + 1) % m]);
}
printf("%.3f\n", solve());
return 0;
}