102593: [AtCoder]ABC259 D - Circumferences
Description
Score : $400$ points
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.
Input
题意翻译
已给出 $n$ 个在平面直角坐标系上的圆。对于每个 $i \in \{1, 2, 3, ..., 4\}$,有第 $i$ 个圆的圆心是 $(x_i, y_i)$,半径是 $r_i$。你需要回答你是否能从 $(s_x, s_y)$ 在圆上连续地走到 $(t_x, t_y)$。Output
分数:400分
问题描述
给你 $N$ 个在 $xy$ 坐标平面上的圆。对于每个 $i = 1, 2, \ldots, N$,第 $i$ 个圆的圆心位于 $(x_i, y_i)$,半径为 $r_i$。
确定是否可以从 $(s_x, s_y)$ 到达 $(t_x, t_y)$,仅通过位于 $N$ 个圆的周长上的点。
约束条件
- $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
。
注意,判断是区分大小写的。
样例输入 1
4 0 -2 3 3 0 0 2 2 0 2 2 3 1 -3 3 3
样例输出 1
Yes
以下是从 $(0, -2)$ 到 $(3, 3)$ 的一种方式。
- 从 $(0, -2)$,逆时针通过第 $1$ 个圆的周长到达 $(1, -\sqrt{3})$。
- 从 $(1, -\sqrt{3})$,顺时针通过第 $2$ 个圆的周长到达 $(2, 2)$。
- 从 $(2, 2)$,逆时针通过第 $3$ 个圆的周长到达 $(3, 3)$。
因此,应该打印 Yes
。
样例输入 2
3 0 1 0 3 0 0 1 0 0 2 0 0 3
样例输出 2
No
不可能仅通过位于至少一个圆的周长上的点从 $(0, 1)$ 到达 $(0, 3)$,所以应该打印 No
。