Problem:

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



Sample input:
1 2 2 1
4 1
0 0
2 0
2 2
0 2


Sample output:
0.2500000000

Submission status: Accepted

Solution code:
# 参考 http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3277276#1
from math import acos, hypot, isclose, sqrt

def intersection(circle, polygon):
    # 円と多角形の共通部分の面積
    # 多角形の点が反時計回りで与えられれば正の値、時計回りなら負の値を返す
    x, y, r = circle
    polygon = [(xp-x, yp-y) for xp, yp in polygon]
    area = 0.0
    for p1, p2 in zip(polygon, polygon[1:] + [polygon[0]]):
        ps = seg_intersection((0, 0, r), (p1, p2))
        for pp1, pp2 in zip([p1] + ps, ps + [p2]):
            c = cross(pp1, pp2)  # pp1 と pp2 の位置関係によって正負が変わる
            if c == 0:  # pp1, pp2, 原点が同一直線上にある場合
                continue
            d1 = hypot(*pp1)
            d2 = hypot(*pp2)
            if le(d1, r) and le(d2, r):
                area += c / 2  # pp1, pp2, 原点を結んだ三角形の面積
            else:
                t = acos(dot(pp1, pp2) / (d1 * d2))  # pp1-原点とpp2-原点の成す角
                sign = 1.0 if c >= 0 else -1.0
                area += sign * r * r * t / 2  # 扇形の面積
    return area

def cross(v1, v2):  # 外積
    x1, y1 = v1
    x2, y2 = v2
    return x1 * y2 - x2 * y1

def dot(v1, v2):  # 内積
    x1, y1 = v1
    x2, y2 = v2
    return x1 * x2 + y1 * y2

def seg_intersection(circle, seg):
    # 円と線分の交点（円の中心が原点でない場合は未検証）
    x0, y0, r = circle
    p1, p2 = seg
    x1, y1 = p1
    x2, y2 = p2

    p1p2 = (x2 - x1) ** 2 + (y2 - y1) ** 2
    op1 = (x1 - x0) ** 2 + (y1 - y0) ** 2
    rr = r * r
    dp = dot((x1 - x0, y1 - y0), (x2 - x1, y2 - y1))

    d = dp * dp - p1p2 * (op1 - rr)
    ps = []

    if isclose(d, 0.0, abs_tol=1e-9):
        t = -dp / p1p2
        if ge(t, 0.0) and le(t, 1.0):
            ps.append((x1 + t * (x2 - x1), y1 + t * (y2 - y1)))
    elif d > 0.0:
        t1 = (-dp - sqrt(d)) / p1p2
        if ge(t1, 0.0) and le(t1, 1.0):
            ps.append((x1 + t1 * (x2 - x1), y1 + t1 * (y2 - y1)))
        t2 = (-dp + sqrt(d)) / p1p2
        if ge(t2, 0.0) and le(t2, 1.0):
            ps.append((x1 + t2 * (x2 - x1), y1 + t2 * (y2 - y1)))

    # assert all(isclose(r, hypot(x, y)) for x, y in ps)
    return ps

def le(f1, f2):  # less equal
    return f1 < f2 or isclose(f1, f2, abs_tol=1e-9)

def ge(f1, f2):  # greater equal
    return f1 > f2 or isclose(f1, f2, abs_tol=1e-9)

N, cx, cy, r = map(int, input().split())
ans = 0
from math import pi
circle_area = pi * r * r
for _ in range(N):
    p, score = map(int, input().split())
    ps = []
    for _ in range(p):
        x, y = map(int, input().split())
        ps.append((x, y))
    area = intersection((cx, cy, r), ps)
    ans += abs(area) * score / circle_area

print(f"{ans:.10f}")