Circles - Intersection of a Circle and a Polygon

Time Limit : 1 sec, Memory Limit : 131072 KB

円と多角形の共通部分

中心が (0, 0) 半径が $r$ の円$c$と、$n$ 個の頂点からなる多角形$g$の共通部分(Intersection)の面積を求めてください。

多角形 $g$ は隣合う点 $p_i$ と $p_{i+1}$ ($1 \leq i \leq n−1$) を結ぶ線が多角形 $g$ の辺になるような点の列 $p_1$, $p_2$,..., $p_n$ で表されます。点 $p_n$ と $p_1$ を結ぶ線も多角形 $g$ の辺となります。 $g$ は凸多角形とは限らないことに注意してください。

Input

入力は以下の形式で与えられる。

$n$ $r$
$x_1$ $y_1$
$x_2$ $y_2$
:
$x_n$ $y_n$

1行目の n は多角形の点の数を表します。点 $p_i$ の座標は2つの整数 $x_i$, $y_i$ で与えられます。点は、多角形の隣り合った点を反時計回りに訪問するような順番で与えられます。入力はすべて整数で与えられます。

Constraints

  • $3 \leq n \leq 100$
  • $1 \leq r \leq 100$
  • $-100 \leq x_i, y_i \leq 100$

Output

面積を1行に出力する。出力値は 0.00001 以下の誤差を許容する。

Sample Input 1

3 5
1 1
4 1
5 5

Sample Output 1

4.639858417607

Sample Input 2

4 5
0 0
-3 -6
1 -3
5 -4

Sample Output 2

11.787686807576