{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003ch3\u003e凸多角形柱工業都市\u003c/h3\u003e\n\n\u003cp\u003e凸多角形柱工業都市 (, ICPC) はいくつかの凸多角形柱の形状をした建物からなる街である.あなたはこの街の中を現在地 \u003ci\u003eS\u003c/i\u003e から目的地 \u003ci\u003eT\u003c/i\u003e に向けて歩こうとしている.今日は日差しが強いので,出来る限りひなたを通らずに目的地へ向かいたい.あなたが立っている地点と太陽を一直線に結んだ線上に建物がある場合,あなたは建物の陰にいるので日差しを受けずにすむ.また,この街の建物の外周には全てひさしが付いているので,建物の外周に沿って歩いている間は,日が当たる縁に沿って歩いても日差しを受けることはない.あなたは建物の内部以外はこの街をどこでも自由に歩くことができる.\n\u003c/p\u003e\n\n\u003cp\u003eもっとも日差しを受けないように現在地から目的地まで歩いた時の,ひなたを歩く距離を出力するプログラムを作成しなさい.\n\u003c/p\u003e\n\n\u003cdiv style\u003d\"text-align:center\"\u003e\n\u003cimg src\u003d\"CDN_BASE_URL/b75691da3523503ba539ac420ecf2717?v\u003d1715808423\" witdh\u003d\"300\" height\u003d\"300\"\u003e\n \u003cp\u003e図E1: 第1インプットの場合\n \u003c/p\u003e\n\u003c/div\u003e\n\n\u003cdiv style\u003d\"text-align:center\"\u003e\n\u003cimg src\u003d\"CDN_BASE_URL/97964cbbfcbe950c4783f4baab013fad?v\u003d1715808423\" witdh\u003d\"300\" height\u003d\"300\"\u003e\n \u003cp\u003e図E2: 第2インプットの場合\n \u003c/p\u003e\n\u003c/div\u003e\n\n\u003cdiv style\u003d\"text-align:center\"\u003e\n\u003cimg src\u003d\"CDN_BASE_URL/6954a8c60436d580213d744bf1ca2659?v\u003d1715808423\" witdh\u003d\"300\" height\u003d\"300\"\u003e\n \u003cp\u003e図E3: 第3インプットの場合\n \u003c/p\u003e\n\u003c/div\u003e\n\n\n\u003ch3\u003eInput\u003c/h3\u003e\n\n\u003cp\u003e入力は複数のデータセットからなる.\nデータセットの個数は最大でも 30 個を超えない.\n各データセットは次の形式で表される.\n\u003c/p\u003e\u003cblockquote\u003e\u003ci\u003eN\u003c/i\u003e\u003cbr\u003e\u003ci\u003eNV\u003csub\u003e1\u003c/sub\u003e\u003c/i\u003e \u003ci\u003eH\u003csub\u003e1\u003c/sub\u003e\u003c/i\u003e \u003ci\u003eX\u003csub\u003e1,1\u003c/sub\u003e\u003c/i\u003e \u003ci\u003eY\u003csub\u003e1,1\u003c/sub\u003e\u003c/i\u003e \u003ci\u003eX\u003csub\u003e1,2\u003c/sub\u003e\u003c/i\u003e \u003ci\u003eY\u003csub\u003e1,2\u003c/sub\u003e\u003c/i\u003e ... \u003ci\u003eX\u003csub\u003e1,NV\u003csub\u003e1\u003c/sub\u003e\u003c/sub\u003e\u003c/i\u003e \u003ci\u003eY\u003csub\u003e1,NV\u003csub\u003e1\u003c/sub\u003e\u003c/sub\u003e\u003c/i\u003e\u003cbr\u003e...\u003cbr\u003e\u003ci\u003eNV\u003csub\u003eN\u003c/sub\u003e\u003c/i\u003e \u003ci\u003eH\u003csub\u003eN\u003c/sub\u003e\u003c/i\u003e \u003ci\u003eX\u003csub\u003eN,1\u003c/sub\u003e\u003c/i\u003e \u003ci\u003eY\u003csub\u003eN,1\u003c/sub\u003e\u003c/i\u003e \u003ci\u003eX\u003csub\u003eN,2\u003c/sub\u003e\u003c/i\u003e \u003ci\u003eY\u003csub\u003eN,2\u003c/sub\u003e\u003c/i\u003e ... \u003ci\u003eX\u003csub\u003eN,NV\u003csub\u003eN\u003c/sub\u003e\u003c/sub\u003e\u003c/i\u003e \u003ci\u003eY\u003csub\u003eN,NV\u003csub\u003eN\u003c/sub\u003e\u003c/sub\u003e\u003c/i\u003e\u003cbr\u003e\u003ci\u003eθ\u003c/i\u003e \u003ci\u003eφ\u003c/i\u003e\u003cbr\u003e\u003ci\u003eS\u003csub\u003ex\u003c/sub\u003e\u003c/i\u003e \u003ci\u003eS\u003csub\u003ey\u003c/sub\u003e\u003c/i\u003e \u003ci\u003eT\u003csub\u003ex\u003c/sub\u003e\u003c/i\u003e \u003ci\u003eT\u003csub\u003ey\u003c/sub\u003e\u003c/i\u003e\u003cbr\u003e\u003c/blockquote\u003e\n\u003cp\u003e1行目の \u003ci\u003eN\u003c/i\u003e は建物の数を表す.続く \u003ci\u003eN\u003c/i\u003e 行は各建物の形状を指定する.\u003ci\u003eNV\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e は \u003ci\u003ei\u003c/i\u003e 番目の建物を上から見た多角形の頂点数,\u003ci\u003eH\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e は \u003ci\u003ei\u003c/i\u003e 番目の建物の高さを表す.\u003ci\u003eX\u003csub\u003ei, j\u003c/sub\u003e\u003c/i\u003e と \u003ci\u003eY\u003csub\u003ei, j\u003c/sub\u003e\u003c/i\u003e は \u003ci\u003ei\u003c/i\u003e 番目の建物を上から見た多角形の \u003ci\u003ej\u003c/i\u003e 番目の頂点の \u003ci\u003ex\u003c/i\u003e 座標と \u003ci\u003ey\u003c/i\u003e 座標を表す.頂点は反時計回りの順で与えられる.全ての建物は上から見ると凸多角形であり,建物の内部に他の建物があったり,頂点や辺が他の多角形と重なったりすることはない.続く行には太陽の方向を表す \u003ci\u003eθ\u003c/i\u003e と \u003ci\u003eφ\u003c/i\u003e が与えられ,\u003ci\u003eθ\u003c/i\u003e は太陽の向きを \u003ci\u003ex\u003c/i\u003e の正の方向から反時計回りの角度で表し,\u003ci\u003eφ\u003c/i\u003e は地平線からの太陽の仰角,すなわち太陽を見上げた時の視線の方向と地表面がなす角度を表す.ただし,太陽は無限遠にあり,移動中には位置を変えないものとする.続く行には現在地と目的地の座標, (\u003ci\u003eS\u003csub\u003ex\u003c/sub\u003e\u003c/i\u003e, \u003ci\u003eS\u003csub\u003ey\u003c/sub\u003e\u003c/i\u003e) と (\u003ci\u003eT\u003csub\u003ex\u003c/sub\u003e\u003c/i\u003e, \u003ci\u003eT\u003csub\u003ey\u003c/sub\u003e\u003c/i\u003e) が与えられる.\n\u003c/p\u003e\u003cblockquote\u003e\u003c/blockquote\u003e\n\u003cp\u003e入力で与えられる数値は全て整数であり,以下の条件を満たす.\n\u003c/p\u003e\u003cblockquote\u003e\u003ci\u003e1 ≤ N ≤ 100\u003c/i\u003e\u003cbr\u003e\u003ci\u003e3 ≤ NV\u003csub\u003ei\u003c/sub\u003e ≤ 12\u003c/i\u003e\u003cbr\u003e\u003ci\u003e1 ≤ H\u003csub\u003ei\u003c/sub\u003e ≤ 1,000\u003c/i\u003e\u003cbr\u003e\u003ci\u003e0 ≤ θ \u0026lt; 360\u003c/i\u003e\u003cbr\u003e\u003ci\u003e0 \u0026lt; φ \u0026lt; 90\u003c/i\u003e\u003c/blockquote\u003e\n\u003cp\u003e座標は全て \u003ci\u003e-1,000\u003c/i\u003e 以上 \u003ci\u003e1,000\u003c/i\u003e 以下である.\n現在地と目的地は異なり,どちらも建物の内部及び外周には存在しない.\n\u003c/p\u003e\u003cblockquote\u003e\u003c/blockquote\u003e\n\u003cp\u003e入力の終わりは,1つのゼロからなる行で表される.\n\u003c/p\u003e\u003cblockquote\u003e\u003c/blockquote\u003e\n\n\n\u003ch3\u003eOutput\u003c/h3\u003e\n\n\n\u003cp\u003e各データセットについて,ひなたを歩く最短距離を1行に出力せよ.出力には 0.001 を超える絶対誤差があってはならない.\n\u003c/p\u003e\u003cblockquote\u003e\u003c/blockquote\u003e\n\n\n\u003ch3\u003eSample Input\u003c/h3\u003e\n\n\u003cpre\u003e2\n4 1 0 0 1 0 1 1 0 1\n4 2 2 2 3 2 3 3 2 3\n60 45\n-1 -1 4 4\n4\n4 1 0 0 3 1 1 2 0 1\n3 2 10 7 8 2 12 4\n6 8 7 12 8 13 9 15 10 19 11 24 10 25\n5 4 16 2 16 4 12 8 14 2 15 0\n167 38\n3 3 15 21\n12\n4 3 -8 -3 -9 -3 -9 -5 -8 -6\n4 5 -4 -5 -7 -5 -7 -6 -5 -6\n4 2 -4 1 -5 1 -5 -4 -4 -4\n4 1 -1 1 -2 1 -2 -4 -1 -3\n4 2 2 3 -1 3 -2 2 3 2\n4 1 3 1 2 1 2 -3 3 -4\n4 7 1 0 0 0 0 -1 1 -1\n4 4 9 5 7 5 7 4 10 4\n4 3 6 5 5 4 5 0 6 0\n4 5 8 -1 5 -1 6 -2 8 -2\n4 1 10 0 9 0 9 -2 10 -1\n4 6 10 2 8 2 8 1 10 1\n131 78\n-10 10 10 -10\n0\n\u003c/pre\u003e\n\n\u003ch3\u003eOutput for Sample Input\u003c/h3\u003e\n\n\u003cpre\u003e1.93185\n7.87174\n20.86840\u003c/pre\u003e"}}]}