当前没有测试数据。

D - 圆

分数: $400$ 分

问题描述

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

判断是否可以通过只经过至少一个圆的圆周上的点从 $(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$ 个圆的圆周上。
• $(t_x, t_y)$ 在 $N$ 个圆的圆周上。
• 所有输入中的值均为整数。

输入

输入以以下格式从标准输入给出：

$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。 注意评测程序区分大小写。

4
0 -2 3 3
0 0 2
2 0 2
2 3 1
-3 3 3

Yes

以下是一种从 $(0, -2)$ 到 $(3, 3)$ 的路径。

• 从 $(0, -2)$，逆时针经过第一个圆的圆周到达 $(1, -\sqrt{3})$。
• 从 $(1, -\sqrt{3})$，顺时针经过第二个圆的圆周到达 $(2, 2)$。
• 从 $(2, 2)$，逆时针经过第三个圆的圆周到达 $(3, 3)$。

因此，应该输出 Yes。

3
0 1 0 3
0 0 1
0 0 2
0 0 3

No

无法通过只经过所有圆的圆周上的点从 $(0, 1)$ 到达 $(0, 3)$，因此应该输出 No。