Magical Circle

Time Limit : 3 sec, Memory Limit : 65536 KB

魔法陣

Problem Statement

〜魔法陣の描き方〜

  1. 十分広くて真っ白な床を用意します.
  2. 床の座標 (0,0) の点を中心にして,半径 1, 2, ..., R の円を描きます.
  3. 半径 1 の円と半径 2 の円の間,半径 3 の円と半径 4 の円の間,... を青色で塗ります.なお,半径 R の円の外には色を塗ってはいけません.
  4. 床に頂点数 N の多角形を一つ描きます.
  5. 多角形の内部の白色の領域を青色で,青色の領域を白色で塗りなおします.

魔法陣の力は,魔法陣に青色が多く含まれるほど強くなるという.
そこであなたには,魔法陣に含まれる青い領域の面積を求めてほしい.

次の図はこの手順で描くことのできる魔法陣の一例である.

Input

入力は以下の形式に従う.与えられる数は全て整数である.

N R
x_1 y_1
...
x_N y_N

(x_i, y_i) は多角形の i 番目の頂点である.

Constraints

  • 3 ≦ N ≦ 100
  • 1 ≦ R ≦ 100
  • 多角形は半径 R の円の内部または円周上に含まれる.
  • 多角形は自己交差をもたない.
  • 多角形の頂点は反時計回りの順番で与えられる.

Output

青い領域の面積を 1 行に出力せよ.
出力する値は,真の値との絶対誤差または相対誤差が 10^{-8} 未満でなければならない.

Sample Input 1

3 1
0 0
1 0
0 1

Output for the Sample Input 1

0.500000000

Sample Input 2

3 2
0 0
2 0
0 2

Output for the Sample Input 2

8.995574288

Sample Input 3

3 2
1 -1
1 1
-2 0

Output for the Sample Input 3

11.123246567

Sample Input 4

4 3
1 1
-1 1
-1 -1
1 -1

Output for the Sample Input 4

11.707963268

Source: Ritsumeikan University Competitive Programming Camp 2013, Day2 , Problem set from Osaka University teams, Shiga, Japan, 2013-03-12
Problem Setter:  fura2