题目描述

Your local art gallery is about to host an exciting new exhibition of sculptures by world-renowned artists, and the gallery expects to attract thousands of visitors. Unfortunately, the exhibition might also attract the wrong kind of visitors, namely burglars who intend to steal the works of art. In the past, the gallery directors did not worry much about this problem, since their permanent collection is, to be honest, not really worth stealing.

The gallery consists of rooms, and each sculpture in the new exhibition will be placed in a different room. Each room has a security guard and an alarm to monitor the artwork. When an alarm sounds, the guard will run (without leaving the room) from their post to a position where they can see the sculpture directly. This is to check whether the sculpture has in fact been stolen, or whether this is yet another false alarm.

To figure out where to best station the security guard, the gallery directors would like to know how long it takes for the guard to see a given sculpture. They hope that you can help!

Every room is on a single floor, and the layout of the walls can be approximated by a simple polygon. The locations of the guard and the sculpture are distinct points strictly inside the polygon. The sculpture is circular, with a negligibly small (but positive) radius. To verify that the sculpture is still present, the guard needs to be able to see at least half of it.

Figure D.1 illustrates two examples. In each case, the guard starts at the blue square on the left, and the sculpture is located at the red circle on the right. The dotted blue line shows the optimal path for the guard to move. Once the guard reaches the location marked by the green diamond, half of the sculpture can be seen.

输入格式

The first line of input contains an integer $n$ ($3 \leq n \leq 100$), the number of vertices that describe the polygon. This is followed by $n$ lines each containing two integers $x$ and $y$ ($0 \leq x,y \leq 1000$), giving the coordinates of the polygon vertices in counterclockwise order. The next line contains two integers $x_g$ and $y_g$, which specify the location of the guard. Finally, the last line contains two integers $x_s$ and $y_s$, which specify the location of the center of the sculpture. The polygon is simple, that is, its vertices are distinct and no two edges of the polygon intersect or touch, other than consecutive edges which touch at their common vertex. In addition, no two consecutive edges are collinear.

输出格式

Output the minimum distance that the guard has to move to be able to see at least half the sculpture. Your answer must have an absolute or relative error of at most $10^{-6}$.

题目大意

简要题意

给定封闭的 $n$ 边形不透明墙壁和其中两个点 $A, B$. 其中，$B$ 是一个半径充分小但大于 $0$ 的透明圆的圆心, 墙壁厚度可视为 $0$. 求所有能直接观察到 $\odot B$ 的至少一半的位置中, 与点 $A$ 距离的最小值.

输入格式

第一行, 一个整数 $n$.

随后 $n$ 行, 每行两个整数 $x_i, y_i$, 依次表示其顶点的坐标。

随后一行, 两个整数 $x_A, y_A$, 表示点 $A$ 的坐标.

最后一行, 两个整数 $x_B, y_B$, 表示圆心 $B$ 的坐标.

输出格式

一行，一个实数，表示最小距离。与标准答案误差不超过 $10^{-6}$ 即可判为正确。

8
0 0
20 0
20 30
60 30
60 0
80 0
80 50
0 50
10 10
70 10

58.137767414995

11
0 0
4 0
4 1
5 1
5 0
7 0
7 2
3 2
3 1
2 2
0 2
1 1
6 1

2.000000000000