Question
Circles
There is a game consisting of N circles on the xy- coordinate plane. For each i=1, 2, …, N, the i- th circle is centered at (xi, yi) and has a radius of ri.
Alice loves this game. But he does not want to lose.
To win this game Alice have to find a way to get from (sx, sy) to (tx, ty) by only passing through points that lie on the circumference of at least one of the N circles.
Determine whether Alice can win or not.
Alice loves this game. But he does not want to lose.
To win this game Alice have to find a way to get from (sx, sy) to (tx, ty) by only passing through points that lie on the circumference of at least one of the N circles.
Determine whether Alice can win or not.
Input
The first line of the input contains a single integer N.
The second line of the input contains 4 integers sx, sy, tx, ty.
The next N lines contains 3 integers xi, yi, ri.
Constraints:
1<=N<=3000
−10^9<=xi, yi<=10^9
1 <= ri <= 10^9
(sx, sy) lies on the circumference of at least one of the N circles.
(tx, ty) lies on the circumference of at least one of the N circles.
All values in input are integers.
The second line of the input contains 4 integers sx, sy, tx, ty.
The next N lines contains 3 integers xi, yi, ri.
Constraints:
1<=N<=3000
−10^9<=xi, yi<=10^9
1 <= ri <= 10^9
(sx, sy) lies on the circumference of at least one of the N circles.
(tx, ty) lies on the circumference of at least one of the N circles.
All values in input are integers.
Output
If Alice wins, print Yes; otherwise, print No.
Note that the judge is case- sensitive.
Note that the judge is case- sensitive.
Example
Sample Input 1:
4
0 -2 3 3
0 0 2
2 0 2
2 3 1
-3 3 3
Sample Output 1:
Yes
Explanation 1:
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, −3).
From (1, −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
Explanation 2:
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.
4
0 -2 3 3
0 0 2
2 0 2
2 3 1
-3 3 3
Sample Output 1:
Yes
Explanation 1:
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, −3).
From (1, −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
Explanation 2:
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.