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
124
|
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#define rep(x,y,z) for (int x=(y);(x)<=(z);(x)++)
#define per(x,y,z) for (int x=(y);(x)>=(z);(x)--)
#define log2(x) (31-__builtin_clz(x))
#define mod (int)(1e9+7)
#define inf 0x3f3f3f3f
#define cls(x) memset(x,0,sizeof(x))
#ifdef DEBUG
#define debugdo(X) X
#define debugndo(X)
#define debugout(X) cout<<(#X)<<"="<<(X)<<endl
#else
#define debugdo(X)
#define debugndo(X) X
#define debugout(X)
#endif
#ifdef ONLINE_JUDGE
#define debugdo(X)
#define debugndo(X)
#define debugout(X)
#endif
#define putarray(x,n) rep(iiii,1,n) printf("%d ",x[iiii])
#define mp make_pair
using namespace std;
typedef pair<int,int> pairs;
typedef long long LL;
const double eps=0.000000001,pi=3.1415926535897932384626433832795028841971693993751058209749446;
template <typename T>
inline void read(T &x){char ch;x=0;bool flag=false;ch=getchar();while (ch>'9'||ch<'0') {if (ch=='-') flag=true;ch=getchar();}while ((ch<='9'&&ch>='0')){x=x*10+ch-'0';ch=getchar();}if (flag) x*=-1;}
template <typename T>
inline void read(T &x,T &y){read(x);read(y);}
template <typename T>
inline void read(T &x,T &y,T &z){read(x);read(y);read(z);}
const int maxn=555;
int n,cnt,tot,m;
double x,y;
#define angel angle
struct Point
{
double x,y;
Point(double a=0,double b=0):x(a),y(b){}
inline Point operator-(const Point &b)const{return Point(x-b.x,y-b.y);}
inline double operator*(const Point &b)const{return x*b.y-y*b.x;}
}res[maxn];
inline double mul(Point a,Point b,Point c){return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);}
struct Line
{
Point x,y;
double angle;
Line(Point a=Point(0,0),Point b=Point(0,0),double c=0):x(a),y(b),angel(c){}
inline bool operator<(const Line &b)const{return abs(angel-b.angel)<eps?mul(x,b.x,b.y)>0:angle<b.angel;}
inline bool operator==(const Line &b)const{return abs(angle-b.angel)<eps;}
}line[maxn];
inline bool right(const Point &a,const Point &b){return a*b<0;}
inline Point intersect(Line a,Line b)
{
double k1=(b.y-a.x)*(a.y-a.x);
double k2=(a.y-a.x)*(b.x-a.x);
double k=k1/(k1+k2);
return Point(b.y.x+(b.x.x-b.y.x)*k,b.y.y+(b.x.y-b.y.y)*k);
}
inline bool judge(Line a,Line b,Line c)
{
Point temp=intersect(a,b);
return (c.y-c.x)*(temp-c.x)<0;
}
int deq[maxn],L,R;
void hpi(Line *a,int n)
{
sort(a+1,a+n+1);
n=unique(a+1,a+n+1)-a-1;
L=0,R=1;
deq[0]=1;deq[1]=2;
rep(i,3,n)
{
while (L<R&&judge(a[deq[R-1]],a[deq[R]],a[i])) R--;
while (L<R&&judge(a[deq[L+1]],a[deq[L]],a[i])) L++;
deq[++R]=i;
}
while (L<R&&judge(a[deq[R-1]],a[deq[R]],a[deq[L]])) R--;
while (L<R&&judge(a[deq[L+1]],a[deq[L]],a[deq[R]])) L++;
deq[++R]=deq[L];
rep(i,L,R-1) res[++tot]=intersect(a[deq[i]],a[deq[i+1]]);
}
int main()
{
read(n);
rep(i,1,n)
{
read(m);
double formerx,formery,xwhenstart,ywhenstart;
scanf("%lf%lf",&formerx,&formery);
xwhenstart=formerx;
ywhenstart=formery;
rep(j,1,m-1)
{
scanf("%lf%lf",&x,&y);
line[++cnt]=Line(Point(formerx,formery),Point(x,y),atan2(formerx-x,formery-y));
formerx=x;formery=y;
}
line[++cnt]=Line(Point(formerx,formery),Point(xwhenstart,ywhenstart),atan2(formerx-xwhenstart,formery-ywhenstart));
}
hpi(line,cnt);
double ans=0;
rep(i,1,tot-1)
ans+=res[i+1]*res[i]/2;
ans+=res[1]*res[tot]/2;
if (tot<=2)
{
puts("0.000");
return 0;
}
printf("%.3lf\n",ans);
return 0;
}
|