/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 400 点
問題文
xy -平面上の N 個の円が与えられます。 i = 1, 2, \ldots, N について、i 番目の円は点 (x_i, y_i) を中心とする半径 r_i の円です。
N 個の円のうち少なくとも 1 つ以上の円の円周上にある点のみを通って、点 (s_x, s_y) から点 (t_x, t_y) に行くことができるかどうかを判定してください。
制約
- 1 \leq N \leq 3000
- -10^9 \leq x_i, y_i \leq 10^9
- 1 \leq r_i \leq 10^9
- (s_x, s_y) は N 個の円のうち少なくとも 1 つ以上の円の円周上にある
- (t_x, t_y) は N 個の円のうち少なくとも 1 つ以上の円の円周上にある
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N s_x s_y t_x t_y x_1 y_1 r_1 x_2 y_2 r_2 \vdots x_N y_N r_N
出力
点 (s_x, s_y) から点 (t_x, t_y) に行くことができる場合は Yes を、そうでない場合は No を出力せよ。
ジャッジは英小文字と英大文字を厳密に区別することに注意せよ。
入力例 1
4 0 -2 3 3 0 0 2 2 0 2 2 3 1 -3 3 3
出力例 1
Yes
例えば、下記の経路で点 (0, -2) から点 (3, 3) へ行くことができます。
- 点 (0, -2) から 1 つ目の円の円周上を反時計回りに通って点 (1, -\sqrt{3}) へ行く。
- 点 (1, -\sqrt{3}) から 2 つ目の円の円周上を時計回りに通って点 (2, 2) へ行く。
- 点 (2, 2) から 3 つ目の円の円周上を反時計回りに通って点 (3, 3) へ行く。
よって、Yes を出力します。
入力例 2
3 0 1 0 3 0 0 1 0 0 2 0 0 3
出力例 2
No
少なくとも 1 つ以上の円の円周上にある点のみを通って点 (0, 1) から点 (0, 3) に行くことはできないので No を出力します。
Score : 400 points
Problem Statement
You are given N circles on the xy-coordinate plane. For each i = 1, 2, \ldots, N, the i-th circle is centered at (x_i, y_i) and has a radius of r_i.
Determine whether it is possible to get from (s_x, s_y) to (t_x, t_y) by only passing through points that lie on the circumference of at least one of the N circles.
Constraints
- 1 \leq N \leq 3000
- -10^9 \leq x_i, y_i \leq 10^9
- 1 \leq r_i \leq 10^9
- (s_x, s_y) lies on the circumference of at least one of the N circles.
- (t_x, t_y) lies on the circumference of at least one of the N circles.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N s_x s_y t_x t_y x_1 y_1 r_1 x_2 y_2 r_2 \vdots x_N y_N r_N
Output
If it is possible to get from (s_x, s_y) to (t_x, t_y), print Yes; otherwise, print No.
Note that the judge is case-sensitive.
Sample Input 1
4 0 -2 3 3 0 0 2 2 0 2 2 3 1 -3 3 3
Sample Output 1
Yes
Here is one way to get from (0, -2) to (3, 3).
- From (0, -2), pass through the circumference of the 1-st circle counterclockwise to reach (1, -\sqrt{3}).
- From (1, -\sqrt{3}), pass through the circumference of the 2-nd circle clockwise to reach (2, 2).
- From (2, 2), pass through the circumference of the 3-rd circle counterclockwise to reach (3, 3).
Thus, Yes should be printed.
Sample Input 2
3 0 1 0 3 0 0 1 0 0 2 0 0 3
Sample Output 2
No
It is impossible to get from (0, 1) to (0, 3) by only passing through points on the circumference of at least one of the circles, so No should be printed.