Circumferences

题目描述

你有 $N$ 个圆在 $xy$-坐标平面上。 对于每个 $i = 1, 2, \ldots, N$，第 $i$ 个圆的圆心在 $(x_i, y_i)$，半径为 $r_i$。 判断是否可以仅通过位于至少一个这 $N$ 个圆的圆周上的点，从 $(s_x, s_y)$ 到达 $(t_x, t_y)$。

输入格式

输入以标准输入给出，格式如下： $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

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

No

提示

$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$ 个圆的圆周上。 输入中的所有数值均为整数。 下面是从 $(0, -2)$ 到 $(3, 3)$ 的一种路径。

从 $(0, -2)$，沿第 $1$ 个圆的圆周逆时针到达 $(1, -\sqrt{3})$。 从 $(1, -\sqrt{3})$，沿第 $2$ 个圆的圆周顺时针到达 $(2, 2)$。 从 $(2, 2)$，沿第 $3$ 个圆的圆周逆时针到达 $(3, 3)$。

因此，应当输出 $Yes$。
仅通过位于至少一个圆的圆周上的点，无法从 $(0, 1)$ 到达 $(0, 3)$，因此应当输出 $No$。

标签: AtCoder|abc259D

来源

AtCoder|abc259D