← 返回题目列表

AtCoder · abc259_d

G. 周长

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

你被给予 N 上的圆圈 xy- 坐标平面。 对于每个 i = 1, 2, \ldots, N, i第一个圆的中心位于 (x_i, y_i) 的半径为 r_i.

判断是否可以从 (s_x, s_y) to (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) to (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) to (3, 3).

  • 来自 (0, -2),穿过圆周 1-st逆时针转一圈到达 (1, -\sqrt{3}).
  • 来自 (1, -\sqrt{3}),穿过圆周 2-顺时针转一圈即可到达 (2, 2).
  • 来自 (2, 2),穿过圆周 3-rd逆时针转圈到达 (3, 3).

因此, Yes 。


示例输入 2

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

示例输出 2

No

不可能从 (0, 1) to (0, 3) 仅通过至少一个圆的圆周上的点,因此 No 。