008 - オノガワ湖調査

時間制限 1 秒 / メモリ制限 256 MB / 得点 10 / x 0 /


誤差
1e-3
TLE
1sec
MLE
256MB
得点
10

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

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

Input

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

xs ys
xg yg
N
x1 y1
x2 y2
:
xN yN

1行目に調査開始地点xs,ys (0≤xs,ys≤104)、2行目に調査終了地点xg,yg (0 ≤ xg,yg ≤ 104)がすべて整数で与えられる。続く1行に、オノガワ湖の領域を構成する頂点の個数N (3 ≤ N ≤ 100)が与えられる。続くN行に、領域を構成する頂点の座標xi,yi (0 ≤ xi,yi ≤ 104)が、領域の重心の周りに反時計回りに整数で与えられる。 ただし、入力は以下の制約を満たすものとする。

  • 調査開始地点と終了地点は、領域内部にも領域の境界上にもない。
  • 調査開始地点と終了地点は、同じ座標をもたない(xsxg または ysyg)。
  • 同じ座標をもつ頂点は与えられない(i≠jについて、xixj または yiyj)。
  • 領域の面積は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