/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
二次元平面上に N 頂点の凸多角形 C 、点 S=(s_x, s_y), T=(t_x,t_y) があります。 C の頂点は、反時計回りに (x_1,y_1),(x_2,y_2),\ldots,(x_N,y_N) です。 S,T は C の外部にあることが保証されています。
C の外周を除いた内部を通らずに点 S から点 T まで移動するときの最短距離を求めてください。
制約
- 3\leq N \leq 10^5
- |x_i|,|y_i|,|s_x|,|s_y|,|t_x|,|t_y|\leq 10^9
- (x_1,y_1),(x_2,y_2),\ldots,(x_N,y_N) は反時計回りに凸多角形をなす
- C のどの 3 点も同一直線上にない
- S,T は C の外部に存在し、C の外周上にない
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N x_1 y_1 x_2 y_2 \vdots x_N y_N s_x s_y t_x t_y
出力
答えを出力せよ。
なお、真の値との絶対誤差または相対誤差が 10^{-6} 以下であれば正解として扱われる。
入力例 1
4 1 1 3 1 3 3 1 3 0 2 5 2
出力例 1
5.65028153987288474496
最短距離を達成する移動方法の一例を以下の図で示します。
(0,2) \to (1,3) \to(3,3)\to(5,2) と移動すると、点 S から点 T への移動距離が 5.650281... となり、これが最小であることが証明できます。 C の外周上は通れることに注意してください。
なお、絶対誤差または相対誤差が 10^{-6} 以下であれば正解として扱われるので、5.650287 などと出力しても正解と判定されます。
入力例 2
3 0 0 2 0 1 10 3 7 10 3
出力例 2
8.06225774829854965279
Score : 600 points
Problem Statement
On a two-dimensional plane, there is a convex polygon C with N vertices, and points S=(s_x, s_y) and T=(t_x,t_y). The vertices of C are (x_1,y_1),(x_2,y_2),\ldots, and (x_N,y_N) in counterclockwise order. It is guaranteed that S and T are outside the polygon.
Find the shortest distance that needs to be traveled to get from point S to point T without entering the interior of C except for its circumference.
Constraints
- 3\leq N \leq 10^5
- |x_i|,|y_i|,|s_x|,|s_y|,|t_x|,|t_y|\leq 10^9
- (x_1,y_1),(x_2,y_2),\ldots, and (x_N,y_N) form a convex polygon in counterclockwise order.
- No three points of C are colinear.
- S and T are outside C and not on the circumference of C.
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N x_1 y_1 x_2 y_2 \vdots x_N y_N s_x s_y t_x t_y
Output
Print the answer.
Your output is considered correct if the absolute or relative error from the true value is at most 10^{-6}.
Sample Input 1
4 1 1 3 1 3 3 1 3 0 2 5 2
Sample Output 1
5.65028153987288474496
One way to achieve the shortest distance is shown in the following figure.
If you travel as (0,2) \to (1,3) \to(3,3)\to(5,2), the length of the path from point S to point T is 5.650281.... We can prove that it is the minimum. Note that you may enter the circumference of C.
Note that your output is considered correct if the absolute or relative error is at most 10^{-6}. For example, output like 5.650287 is also considered correct.
Sample Input 2
3 0 0 2 0 1 10 3 7 10 3
Sample Output 2
8.06225774829854965279