Lake Survey

Time Limit : 1 sec, Memory Limit : 262144 KB

オノガワ湖調査

アイヅ探検隊は、アイヅ自然保護区の調査を計画している。この調査では、調査開始地点から調査終了地点まで、最短の距離で到達したい。ただし、途中でオノガワ湖の沿岸に立ち寄らなければならない。また、オノガワ湖は沿岸に沿って歩くことはできても、湖に入ることはできない。

調査開始地点と終了地点、凸多角形によって表されるオノガワ湖の領域があたえられたとき、アイヅ探検隊が通るべき最短経路の距離を求めるプログラムを作成せよ。ただし、オノガワ湖では沿岸(領域を構成する辺や点)を通るだけで、内側に入ってはいけない。

Input

入力は以下の形式で与えられる。

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)が、領域の重心の周りに反時計回りに整数で与えられる。 ただし、入力は以下の制約を満たすものとする。

  • 調査開始地点と終了地点は、領域内部にも領域の境界上にもない。
  • 調査開始地点と終了地点は、同じ座標をもたない(x_s≠x_g または y_s≠y_g)。
  • 同じ座標をもつ頂点は与えられない(i≠jについて、x_i≠x_j または y_i≠y_j)。
  • 領域の面積は0より大きい。
  • 領域を構成する頂点のうち、どの3点も1直線上にはない。

Output

アイヅ探検隊が通るべき最短経路の距離を出力する。ただし、誤差がプラスマイナス10-3 を超えてはならない。この条件を満たせば小数点以下何桁表示してもよい。

Sample Input 1

0 0
4 0
4
1 1
2 1
3 3
1 2

Sample Output 1

4.472136

Sample Input 2

4 4
0 0
4
1 1
3 1
3 3
1 3

Sample Output 2

6.32455

Source: PC Koshien 2017 , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2017-11-3
http://web-ext.u-aizu.ac.jp/pc-concours/