BZOJ 2618

传送门

坑Bextended啊啊啊啊啊啊啊凭什么一样的公式算出来的东西还是会有误差啊啊啊啊啊啊

嗯…$n\times m$个半平面求交…没了

PASCAL没有高端的atan2,只能arctan完特判一下…


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
121
122
123
program bzoj_2618;
uses math;
const eps=1e-6;
type point=record x,y:extended; end;
line=record a,b:point; k:extended; end;
var p:array[1..500]of point;
l,s:array[1..500]of line;
n,m,i,j,tot:longint;
ans:extended;
function l_(a,b:point):line;
begin
l_.a:=a;
l_.b:=b;
end;
function cross(l1,l2:line):extended;
begin
exit((l1.b.x-l1.a.x)*(l2.b.y-l2.a.y)-(l2.b.x-l2.a.x)*(l1.b.y-l1.a.y));
end;
function cmp(l1,l2:line):boolean;
begin
if abs(l1.k-l2.k)>eps then exit(l1.k<l2.k);
exit(cross(l1,l_(l1.a,l2.b))>0);
end;
procedure qsort(ll,rr:longint);
var i,j:longint;
mid,p:line;
begin
i:=ll;
j:=rr;
mid:=l[(ll+rr)>>1];
repeat
while cmp(l[i],mid) do inc(i);
while cmp(mid,l[j]) do dec(j);
if i<=j then
begin
p:=l[i];
l[i]:=l[j];
l[j]:=p;
inc(i);
dec(j);
end;
until i>j;
if ll<j then qsort(ll,j);
if i<rr then qsort(i,rr);
end;
procedure unique;
var cnt,i:longint;
begin
qsort(1,tot);
cnt:=0;
for i:=1 to tot do
begin
if (i=1)or(l[i].k-l[i-1].k>eps) then inc(cnt);
l[cnt]:=l[i];
end;
tot:=cnt;
end;
function inter(l1,l2:line):point;
var s1,s2,t:extended;
begin
s1:=cross(l1,l_(l1.a,l2.a));
s2:=cross(l_(l1.a,l2.b),l1);
t:=s1/(s1+s2+eps);
inter.x:=l2.a.x+t*(l2.b.x-l2.a.x);
inter.y:=l2.a.y+t*(l2.b.y-l2.a.y);
end;
function upper(p:point;l:line):boolean;
begin
exit(cross(l,l_(l.a,p))-eps>0);
end;
procedure solve;
var ll,rr,i:longint;
begin
s[1]:=l[1];
s[2]:=l[2];
ll:=1;
rr:=2;
for i:=3 to tot do
begin
while (ll<rr)and(not upper(inter(s[rr-1],s[rr]),l[i])) do dec(rr);
while (ll<rr)and(not upper(inter(s[ll],s[ll+1]),l[i])) do inc(ll);
inc(rr);
s[rr]:=l[i];
end;
while (ll<rr)and(not upper(inter(s[rr-1],s[rr]),s[ll])) do dec(rr);
while (ll<rr)and(not upper(inter(s[ll],s[ll+1]),s[rr])) do inc(ll);
n:=rr-ll+1;
s[rr+1]:=s[ll];
for i:=ll to rr do p[i-ll+1]:=inter(s[i],s[i+1]);
ans:=0;
for i:=2 to n-1 do ans:=ans+cross(l_(p[1],p[i]),l_(p[1],p[i+1]))/2;
end;
begin
readln(n);
tot:=0;
for i:=1 to n do
begin
readln(m);
for j:=1 to m do readln(p[j].x,p[j].y);
p[m+1]:=p[1];
for j:=1 to m do
begin
l[tot+j].a:=p[j];
l[tot+j].b:=p[j+1];
l[tot+j].k:=arctan((p[j+1].y-p[j].y)/(p[j+1].x-p[j].x+eps));
if (p[j].x>p[j+1].x)and(p[j].y<=p[j+1].y) then l[tot+j].k:=pi+l[tot+j].k;
if (p[j].x>p[j+1].x)and(p[j].y>p[j+1].y) then l[tot+j].k:=-pi+l[tot+j].k;
end;
inc(tot,m);
end;
unique;
solve;
writeln(ans:0:3);
end.