← 返回题目列表

Codeforces · 1252/I

I. 可能完成的任务

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

艾伦是一名政府特勤人员,他被指派渗透到一个黑手党秘密基地,以揭露有关黑手党行动的重要信息。

秘密基地是一个在笛卡尔坐标系中以 $$$(x_L,y_L)$$$、$$$(x_L,y_R)$$$、$$$(x_R,y_L)$$$ 和 $$$(x_R,y_R)$$$ 为边界的矩形,其中 $$$x_L < x_R$$$ 且 $$$y_L < y_R$$$。秘密基地内放置了$$$N$$$传感器。 $$$i^{th}$$$传感器位于$$$(x_i, y_i)$$$,有效感应半径为$$$r_i$$$,可以检测到$$$(x_i, y_i)$$$严格位于$$$r_i$$$半径内的任何人。换句话说,当且仅当 $$$(x_i, y_i)$$$ 和 $$$(x_a, y_a)$$$ 的欧几里德距离严格小于 $$$r_i$$$ 时,$$$i^{th}$$$ 传感器才能检测到位置 $$$(x_a, y_a)$$$ 处的人。还已知任意两个传感器 $$$i$$$ 和 $$$j$$$ 的欧几里德距离严格大于 $$$r_i + r_j$$$。请注意,两点 $$$(x_a, y_a)$$$ 和 $$$(x_b, y_b)$$$ 的欧氏距离为 $$$\sqrt{|x_a - x_b|^2 + |y_a - y_b|^2}$$$。

艾伦在地点$$$(x_s, y_s)$$$开始他的渗透任务,他的目标位于$$$(x_t, y_t)$$$。艾伦有能力在直线上跑得极快,但他需要花费额外的时间来改变他的跑步轨迹(调整脚步)。尽管他跑得很快,但他仍然需要确保在他跑步时没有任何传感器检测到他,即他的跑步轨迹中没有点严格位于传感器有效感应半径内。

设$$$P = \{(x_{p_1}, y_{p_1}), \dots, (x_{p_{|P|}}, y_{p_{|P|}})\}$$$为艾伦改变跑步轨迹的位置集合,因此,艾伦与$$$P$$$的跑步轨迹为$$$(x_s, y_s) \rightarrow (x_{p_1}, y_{p_1}) \rightarrow \dots \rightarrow (x_{p_{|P|}}, y_{p_{|P|}}) \rightarrow (x_t, y_t)$$$ 其中 $$$(x_a,y_a) \rightarrow (x_b,y_b)$$$ 意味着 Allen 正在从 $$$(x_a,y_a)$$$ 运行到 $$$(x_b,y_b)$$$ 直线。当且仅当使用 $$$P$$$ 时,艾伦没有被任何传感器检测到并且没有跑出秘密基地(尽管允许艾伦沿着秘密基地周边奔跑),$$$P$$$ 集合才是可行的。请注意,$$$x_p$$$ 和 $$$y_p$$$、$$$(x_p,y_p) \in P$$$ 不一定是整数;它们可以是实数。

此问题中您的任务是找到任何一个可行的 $$$P$$$,其中包含不超过 $$$1000$$$ 点。

输入

输入以包含五个整数的行开头: $$$N$$$ $$$x_L$$$ $$$y_L$$$ $$$x_R$$$ $$$y_R$$$ ($$$0 \le N \le 50$$$; $$$0 \le x_L < x_R \le 1000$$$; $$$0 \le y_L < y_R \le 1000$$$) 分别代表传感器和秘密基地的数量 ($$$x_L$$$, $$$y_L$$$, $$$x_R$$$, $$$y_R$$$)。下一行包含两个整数: $$$x_s$$$ $$$y_s$$$ ($$$x_L < x_s < x_R$$$; $$$y_L < y_s < y_R$$$) 表示 Allen 的初始位置。下一行包含两个整数: $$$x_t$$$ $$$y_t$$$ ($$$x_L < x_t < x_R$$$; $$$y_L < y_t < y_R$$$) 表示 Allen 的目标位置。保证 $$$x_s \ne x_t$$$ 或 $$$y_s \ne y_t$$$。接下来的 $$$N$$$ 行每行包含三个整数: $$$x_i$$$ $$$y_i$$$ $$$r_i$$$ ($$$x_L < x_i - r_i < x_i + r_i < x_R$$$; $$$y_L < y_i - r_i < y_i + r_i < y_R$$$; $$$1 \le r_i \le 1000$$$) 表示位置 $$$(x_i, y_i)$$$ 处的传感器,有效感应半径为 $$$r_i$$$。保证任意两个传感器$$$i$$$和$$$j$$$的欧氏距离大于$$$r_i + r_j$$$。还保证 $$$(x_s,y_s)$$$ 和 $$$(x_t,y_t)$$$ 到任何传感器 $$$i$$$ 的欧几里得距离大于 $$$r_i$$$。

输出

在一行中输出一个整数,表示可行的 $$$P$$$ 的大小。接下来的 $$$|P|$$$ 行每行包含两个实数(用一个空格分隔); $$$j^{th}$$$ 行包含 $$$x_j$$$ $$$y_j$$$ 表示 $$$P$$$ 中的 $$$j^{th}$$$ 点。您可以输出任何可行的$$$P$$$,但点数不超过$$$1000$$$。

由于输出的性质(浮点),让我们将 epsilon $$$\epsilon$$$ 定义为 $$$10^{-6}$$$ 来验证输出。考虑对于所有 $$$1 \le j \le |P|$$$,$$$Q_1 = (x_s, y_s)$$$,$$$Q_{j+1} = P_j$$$,以及 $$$Q_{|P|+2} = (x_t, y_t)$$$。然后,当且仅当 $$$P$$$ 包含不超过 $$$1000$$$ 点并且满足以下所有条件时,$$$P$$$ 被认为是正确的:

- $$$x_L - \epsilon \le x_{p_k} \le x_R + \epsilon$$$ 和 $$$y_L - \epsilon \le y_{p_k} \le y_R + \epsilon$$$ 对于所有 $$$1 \le k \le |P|$$$ (艾伦没有耗尽秘密基地)。
- 对于所有 $$$1 \le k < |Q|$$$,设 $$$S_k$$$ 为连接 $$$Q_k$$$ 和 $$$Q_{k+1}$$$ 的线段(艾伦正在直线奔跑)。对于所有 $$$1 \le i \le N$$$,设 $$$(x_{k,i},y_{k,i})$$$ 为沿 $$$S_k$$$ 距离 $$$i^{th}$$$ 传感器位置最近的点 $$$(x_i,y_i)$$$。令 $$$d_{k,i}$$$ 为 $$$(x_{k,i},y_{k,i})$$$ 和 $$$(x_i,y_i)$$$ 之间的欧几里德距离。然后,应满足约束 $$$r_i \le d_{k,i} + \epsilon$$$ (任何传感器均未检测到 Allen)。
- $$$Q$$$ 中的所有点都是不同的。当且仅当 $$$|x_a - x_b| 时,两个点 $$$(x_a,y_a)$$$ 和 $$$(x_b,y_b)$$$ 被视为不同。 > \epsilon$$$ 或 $$$|y_a - y_b| > \epsilon$$$。

示例

输入 #1

3 2 2 50 26
4 14
48 14
15 13 7
36 16 6
46 18 3

输出 #1

2
13.25 23.1234567
36.591003 7.1

输入 #2

1 0 0 1000 1000
100 501
900 501
500 251 250

输出 #2

0

注意

示例输入/输出#1 的说明

上图显示了示例输出中的 $$$P$$$。请注意,此示例中存在一个可行的 $$$P$$$,只有一个点,尽管您不需要找到这样的 $$$P$$$。