アイヅ探検隊は、アイヅ自然保護区の調査を計画している。この調査では、調査開始地点から調査終了地点まで、最短の距離で到達したい。ただし、途中でオノガワ湖の沿岸に立ち寄らなければならない。また、オノガワ湖は沿岸に沿って歩くことはできても、湖に入ることはできない。
調査開始地点と終了地点、凸多角形によって表されるオノガワ湖の領域があたえられたとき、アイヅ探検隊が通るべき最短経路の距離を求めるプログラムを作成せよ。ただし、オノガワ湖では沿岸(領域を構成する辺や点)を通るだけで、内側に入ってはいけない。
入力は以下の形式で与えられる。
x_s y_s x_g y_g N x_1 y_1 x_2 y_2 : x_N y_N
1行目に調査開始地点x_s,y_s (0≤x_s,y_s≤104)、2行目に調査終了地点x_g,y_g (0 ≤ x_g,y_g ≤ 104)がすべて整数で与えられる。続く1行に、オノガワ湖の領域を構成する頂点の個数N (3 ≤ N ≤ 100)が与えられる。続くN行に、領域を構成する頂点の座標x_i,y_i (0 ≤ x_i,y_i ≤ 104)が、領域の重心の周りに反時計回りに整数で与えられる。 ただし、入力は以下の制約を満たすものとする。
アイヅ探検隊が通るべき最短経路の距離を出力する。ただし、誤差がプラスマイナス10-3 を超えてはならない。この条件を満たせば小数点以下何桁表示してもよい。
0 0 4 0 4 1 1 2 1 3 3 1 2
4.472136
4 4 0 0 4 1 1 3 1 3 3 1 3
6.32455