Minimum Guard Travel Distance for Sculpture Visibility

The local art gallery is hosting an exhibition in a single‐floor gallery whose layout is described by a simple polygon. In the exhibition, each sculpture is placed in its own room; each room has a security guard at a starting position. When an alarm sounds the guard must relocate to a position from which he can verify that the sculpture is still there. To do so, the guard must be able to view at least half of the sculpture’s circumference.

The sculpture is modeled as a circle with a negligible (but positive) radius. It is assumed that the sculpture and the guard’s starting position are strictly inside the polygon. In many cases the layout is such that the sculpture is entirely visible (for example, in a convex polygon). In this simplified version of the problem, you are guaranteed that the polygon is convex so that a direct line‐of-sight exists between any two points inside, and therefore the guard will see the entire sculpture if he goes directly to the sculpture location.

Your task is to determine the minimum distance the guard has to travel inside the polygon in order to reach a position from which at least half of the sculpture is visible. In a convex polygon this is equivalent to the straight–line Euclidean distance from the guard’s starting position to the sculpture’s center.

Note: Although the sculpture is circular, its radius is so small (but positive) that the condition reduces to simply being able to see the sculpture. Hence, for this problem the answer is computed as the Euclidean distance between the guard and the sculpture.

Figure D.1 (not shown here) illustrates two examples. In each case the guard starts at the blue square (guard’s position) and the sculpture is located at the red circle. The optimal route is the straight–line segment to the sculpture.

inputFormat

The input begins with an integer n (n ≥ 3) representing the number of vertices of the polygon. The following n lines each contain two floating–point numbers denoting the coordinates of the polygon's vertices given in order (either clockwise or counterclockwise).

The next line contains two floating–point numbers indicating the guard's starting coordinates.

The last line contains three floating–point numbers. The first two represent the coordinates of the sculpture's center, and the third is the (small) radius of the sculpture.

outputFormat

Output a single floating point number: the minimum distance the guard must travel along a path entirely contained in the polygon to reach a position from which at least half of the sculpture is visible. In this convex polygon setting, this is simply the Euclidean distance from the guard's starting position to the sculpture. Your answer should be accurate up to at least 6 decimal places.

sample

4
0 0
10 0
10 10
0 10
1 1
9 9 0.001

11.313708