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
| #include<cstdio>
#include<cstring>
#include<algorithm>
#define RG register
#define clear(x, y) memset(x, y, sizeof(x));
const double INF(1000.);
const int maxn(10010);
struct point { double x, y; };
struct line { point x, y; };
typedef point vector;
inline vector operator + (const vector &lhs, const vector &rhs)
{ return (vector) {lhs.x + rhs.x, lhs.y + rhs.y}; }
inline vector operator - (const vector &lhs, const vector &rhs)
{ return (vector) {lhs.x - rhs.x, lhs.y - rhs.y}; }
inline vector operator * (const vector &lhs, const double &rhs)
{ return (vector) {lhs.x * rhs, lhs.y * rhs}; }
inline vector operator / (const vector &lhs, const double &rhs)
{ return (vector) {lhs.x / rhs, lhs.y / rhs}; }
inline double operator * (const vector &lhs, const vector &rhs)
{ return lhs.x * rhs.x + lhs.y * rhs.y; }
inline double cross(const vector &lhs, const vector &rhs)
{ return lhs.x * rhs.y - lhs.y * rhs.x; }
point S[maxn]; int top;
point Intersection(line a, line b)
{
point c = b.x - a.x;
double t = cross(b.y, c) / cross(b.y, a.y);
return a.x + a.y * t;
}
inline void prepare()
{
top = 0;
S[++top] = (point) {INF, INF};
S[++top] = (point) {-INF, INF};
S[++top] = (point) {-INF, -INF};
S[++top] = (point) {INF, -INF};
}
void add_line(line a)
{
static point tmp[maxn]; int tot = 0;
S[top + 1] = S[1];
for(RG int i = 1; i <= top; i++)
{
double p = cross(a.y, S[i] - a.x);
double q = cross(a.y, S[i + 1] - a.x);
if(p >= 0) tmp[++tot] = S[i];
if(p * q < 0) tmp[++tot] = Intersection(a, (line) {S[i], S[i + 1] - S[i]});
}
top = tot;
for(RG int i = 1; i <= top; i++) S[i] = tmp[i];
}
point p[maxn];
int main()
{
int T, n; scanf("%d", &T);
prepare();
while(T--)
{
scanf("%d", &n);
for(RG int i = 1; i <= n; i++)
scanf("%lf%lf", &p[i].x, &p[i].y);
p[n + 1] = p[1];
for(RG int i = 1; i <= n; i++)
add_line((line) {p[i], p[i + 1] - p[i]});
}
double ans = 0; S[top + 1] = S[1];
for(RG int i = 2; i <= top; i++) ans += cross(S[i] - S[1], S[i + 1] - S[1]);
printf("%.3lf\n", ans / 2.);
return 0;
}
|