22530번 - Intelligent Circular Perfect Cleaner 스페셜 저지다국어

Automatic Cleaning Machine (ACM) 社は画期的な全自動円形掃除機 Intelligent Circular Perfect Cleaner(ICPC) を開発した． なんとこの ICPC は人がいない日中に自動で動き出し，自分が通り過ぎた場所のゴミを掃除する機能を備えている． 全自動という特性を活かすためにも ICPC の集塵機の容積を大きくし，人手でゴミを捨てる回数を減らしたい． しかしながら ICPC が大型化すればするほど ICPC が円形故に部屋の隅の掃除できない部分の面積も大きくなってしまう．(図G-1)

図G-1

また廊下の幅よりも大きくしてしまうと廊下を通ることができなくなってしまう．(図G-2)

図G-2

ACM 社は凄腕プログラマーのあなたに，部屋の見取り図とICPCの中心座標と半径からその部屋の中でICPCが掃除可能な面積を出力するプログラムの作成を依頼した．

入力は複数のデータセットからなり，各データセットは以下の形式をしている．

n x y r
x1 y1
x2 y2
...
xn yn

データセットの1行目には４つの整数 n , x , y , r が記されており，それぞれ部屋を構成する多角形の頂点数(3 ≤ n ≤ 20)， ICPCの初期位置の中心座標 (-100 ≤ x , y ≤ 100)， ICPCの半径 (1 ≤ r ≤ 100)を表している． 続く n 行には多角形の頂点の座標が反時計回りに記されており，以下の条件を満たす．

• -100 ≤ x_i , y_i ≤ 100
• 全ての壁は，x軸かy軸に並行
• ICPCの初期位置は必ず部屋の内側にあり，どの部屋の壁とも10^-3以上離れている
• 任意の部屋の頂点同士の距離，任意の部屋の頂点と部屋の辺の距離，任意の部屋の辺同士の距離は 2r +10^-3より大きいかもしくは 2r -10^-3より小さい

四つのゼロのみからなる行が入力の終わりを表す．

各データセットに対し，ICPCが掃除可能な領域の面積を1行に出力せよ．答えには10^-6を超える誤差があってはならない．