B - アリの高橋くん
Editorial
/
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
アリの高橋くんは凸多角形状の板の上にいます。 高橋くんは向いている方向にまっすぐ歩いていきますが、どの方向を向いているかはわかりません。 高橋くんは板の周囲にたどり着くと落ちてしまいます。 高橋くんの位置と板を構成する凸多角形の頂点の位置が与えられるので、高橋くんが板から落ちるまでに歩く最短の距離を求めてください。位置は全て2次元座標で与えられます。
入力
入力は以下の形式で標準入力から与えられる。
x y N x_1 y_1 x_2 y_2 : x_N y_N
- 1 行目には、高橋くんがいる位置の座標を表す整数 x, y (-100 ≦ x ≦ 100, -100 ≦ y ≦ 100) が空白区切りで与えられる。
- 2 行目には、板を構成する凸多角形の頂点数を表す整数 N (3 ≦ N ≦ 10) が与えられる。
- 3 行目からの N 行には、板の頂点の座標を表す整数 x_i y_i (-100 ≦ x_i ≦ 100, -100 ≦ y_i ≦ 100) が空白区切りで与えられる。ただし、板の頂点は反時計回りの順で与えられる。
- 高橋くんのいる位置は周囲を含まない板の内部である。
- 板は凸多角形であることが保証される。
出力
高橋くんが板から落ちるまでに歩く最短の距離を 1 行に出力せよ。出力は絶対誤差あるいは相対誤差の少なくとも片方が 10^{−6} 以下であれば許容される。
入力例1
0 0 4 100 100 -100 100 -100 -100 100 -100
出力例1
100
どれかの辺に垂直に歩いて行くと、100 だけ歩いて板から落ちます。
入力例2
10 10 3 0 100 -100 -100 100 -100
出力例2
31.3049516850
入力例3
34 6 7 -43 -65 -23 -99 54 -68 65 92 16 83 -18 43 -39 2
出力例3
25.0284205314