BZOJ

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.