E - 雲と影 解説 /

実行時間制限: 2 sec / メモリ制限: 64 MB

問題文

xy 平面が地面であり，地面から鉛直上向きに z 軸を取る．
この問題では，太陽は点（点光源），雲は厚みのない多角形とみなすことにする．
この世界には太陽が 2 つあり，座標 ({8192}^{65536},\ {8192}^{65536},\ {8192}^{65536}) と (-{8192}^{65536},\ -{8192}^{65536},\ {8192}^{65536}) にある．
雲は，上空 H，つまり， z = H の平面上にあり，複数あっても良い．
雲は太陽の光を遮断し，どちらの太陽の光も届かない地面の場所には影ができる．
今，地面に多角形の形をした影が 1 つできた．
地面にできた影の形が与えられるので，雲の合計面積の最小値を求めてください．

入力

最初の行にはテストケースの数 T が与えられる．
その後の行には T 個のテストケースが続く．

各テストケースの 1 行目には，影の多角形の頂点の数 N と，雲の位置の z 座標の値 H が半角スペース区切りで与えられる．
その後の N 行には，各頂点の x 座標と y 座標が半角スペース区切りで与えられる．
ここで，多角形の頂点は，時計回り，または，反時計回りで与えられる．

制約

  • T,\ N については以下の 2 つの条件のどちらか一方を満たす
    • 0 \leq T \leq 4096 かつ 3 \leq N \leq 16
    • T = 1 かつ N = 2048
  • 1 \leq H \leq 64 で H は整数である
  • 多角形の各頂点の座標の値の絶対値は 32 を超えない
  • 多角形の各頂点の座標の値は小数点以下がちょうど 2 桁であるような小数で与えられる
  • 多角形は単純である．つまり自己交差を持たない
  • 多角形の連続する 3 つの頂点は一直線上にはない

出力

各テストケースに対して，雲の合計面積の最小値を出力してください．
その際，小数第 3 位を四捨五入し，小数第 2 位まで出力してください．

入力例

2
4 5
0.00 1.00
1.00 1.00
1.00 0.00
0.00 0.00
3 64
0.00 1.00
1.00 0.00
0.00 0.00

出力例

2.00
1.00
writer: laycrs