AT_abc259_d [ABC259D] Circumferences

题目描述

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

请判断是否可以仅通过经过至少一个圆的圆周上的点，从点 $(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。请注意，判题时区分英文字母的大小写。

输入输出样例 #1

输入 #1

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

输出 #1

Yes

输入输出样例 #2

输入 #2

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

输出 #2

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$ 个圆中的一个圆的圆周上
• 所有输入均为整数

样例解释 1

例如，可以通过如下路径从点 $(0, -2)$ 到达点 $(3, 3)$。

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

因此，输出 Yes。

样例解释 2

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

由 ChatGPT 4.1 翻译