圆周

题目描述

在 $xy$ 坐标平面上给定 $N$ 个圆。 对于每个 $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
⋮
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$ 个圆的圆周逆时针移动,到达 $(1, -\sqrt{3})$。

从 $(1, -\sqrt{3})$ 出发,沿第 $2$ 个圆的圆周顺时针移动,到达 $(2, 2)$。

从 $(2, 2)$ 出发,沿第 $3$ 个圆的圆周逆时针移动,到达 $(3, 3)$。

因此,应输出 Yes。

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

No

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

数据范围

• $1 \le N \le 3000$
• $-10^9 \le x_i, y_i \le 10^9$
• $1 \le r_i \le 10^9$
• $(s_x, s_y)$ 位于至少一个圆的圆周上。
• $(t_x, t_y)$ 位于至少一个圆的圆周上。
• 输入中的所有值均为整数。