Score : $400$ points

问题描述

给定在 $xy$ 坐标平面上的 $N$ 个圆。对于每个 $i = 1, 2, \ldots, N$，第 $i$ 个圆以点 $(x_i, y_i)$ 为中心，半径为 $r_i$。

确定是否可以从点 $(s_x, s_y)$ 到达点 $(t_x, t_y)$，且仅通过至少位于这 $N$ 个圆之一的圆周上的点。

以上为通义千问 qwen-max 翻译，仅供参考。

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.

update @ 2024/3/10 10:59:35