Yu-kun Likes To Play Darts

Time Limit : 3 sec, Memory Limit : 262144 KB

Problem J: Yu-kun Likes To Play Darts

Background

会津大学付属幼稚園はプログラミングが大好きな子供が集まる幼稚園である。園児の一人であるゆう君は、プログラミングと同じくらいダーツが大好きだ。 そんなゆう君は最近ダーツにはまっていたが、普通のダーツに飽きてしまったため独自のダーツボードを作ることにした。

ダーツについてはダーツを参照。

Problem

ゆう君が考えたダーツの内容は以下の通りだ。

無限に広いダーツボードには得点の書かれた多角形が幾つかある。 プレイヤーはダーツの矢を1本だけ持っている。 プレイヤーは矢を投げ、いずれかの多角形に矢を刺すことでそこに書かれている得点を得る。 それ以外に刺さった場合は得点は得られない。

ゆう君は矢を投げる位置を決めたのだが、正確に刺さるとは限らない。 ダーツボードを2次元平面とし、ゆう君が狙う位置を点(cx,cy)とする。 ゆう君の投げた矢が刺さる場所は、点(cx,cy)を中心とする半径rの円に含まれる任意の点から一様な確率で選ばれる。 ばれる点の座標は整数である必要はない。

ダーツボードの情報とゆう君が狙う位置(cx,cy)、半径rが与えれるので、ゆう君が獲得することの出来る得点の期待値を答えよ。

Input

n cx cy r
0番目の多角形の情報
1番目の多角形の情報
...
(n-1)番目の多角形の情報

nはダーツボード上にある多角形の数である。 多角形の情報は以下の形式で与えられる。

p score
x0 y0
x1 y1
...
x(p-1) y(p-1)

pは多角形の頂点数を表し、scoreは多角形に書かれている得点を表す。 多角形の各線分は(xi,yi)と(xi+1,yi+1) ( i < p-1 )の頂点を繋いだ線分と、(xp-1,yp-1)と(x0,y0)の頂点を繋いだ線分である。

Constraints

入力は以下の条件を満たす。

  • 入力は全て整数で与えられる
  • 1 ≤ n ≤ 50
  • 0 ≤ cx, cy, x, y ≤ 1000
  • 1 ≤ r ≤ 100
  • 3 ≤ p ≤ 10
  • 1 ≤ score ≤ 100
  • 多角形の頂点は、隣り合った頂点を時計回り、または反時計回りに訪問するような順番で与えられる
  • 多角形の辺が別の多角形の辺と共通な点をもつことはない
  • 多角形が別の多角形を内包することはない
  • 矢が多角形の辺上に刺さった場合、得点は得られないものとする

Output

ゆう君が獲得することの出来る得点の期待値を1行で出力せよ。小数点以下は何桁数字を出力しても構わない。ただし、解答の誤差は0.000001(10-6)を超えてはならない。

Sample Input 1

1 2 2 1
4 1
0 0
2 0
2 2
0 2

Sample Output 1

0.2500000000

Sample Input 2

1 2 2 1
4 1
0 0
5 0
5 5
0 5

Sample Output 2

1.0000000000

Sample Input 3

4 3 3 2
3 1
1 1
3 3
1 5
4 2
2 0
5 0
4 2
3 2
3 3
4 3
6 1
6 5
4 4
3 4
4 4
5 6
2 6

Sample Output 3

1.0574955319

Sample Input 4

1 10 10 1
4 10
0 0
1 0
1 1
0 1

Sample Output 4

0.0000000000