The Onogawa Expedition is planning to conduct a survey of the Aizu nature reserve. The expedition planner wants to take the shortest possible route from the start to end point of the survey, while the expedition has to go around the coast of the Lake of Onogawa en route. The expedition walks along the coast of the lake, but can not wade across the lake.
Based on the base information including the start and end point of the survey and the area of Lake Onogawa as convex polygon data, make a program to find the shortest possible route for the expedition and calculate its distance. Note that the expedition can move along the polygonal lines passing through the nodes, but never enter within the area enclosed by the polygon.
The input is given in the following format.
x_s y_s x_g y_g N x_1 y_1 x_2 y_2 : x_N y_N
The first line provides the start point of the survey x_s,y_s (0≤x_s,y_s≤104), and the second line provides the end point x_g,y_g (0 ≤ x_g,y_g ≤ 104) all in integers. The third line provides the number of apexes N (3 ≤ N ≤ 100) of the polygon that represents the lake, and each of the subsequent N lines provides the coordinate of the i-th apex x_i,y_i (0 ≤ x_i,y_i ≤ 104) in counter-clockwise order. These data satisfy the following criteria:
Output the distance of the shortest possible expedition route. Any number of decimal places can be selected as long as the error does not exceed ± 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