CF1252I.Mission Possible

Allen, a government secret service, has been assigned to infiltrate a mafia secret base to uncover crucial information regarding the mafia's operations.

The secret base is a rectangular bounded by $(x_L,y_L)$, $(x_L,y_R)$, $(x_R,y_L)$, and $(x_R,y_R)$ in a Cartesian coordinate system where $x_L \lt x_R$ and $y_L \lt y_R$. There are $N$ sensors placed inside the secret base. The $i^{th}$ sensor is located at $(x_i, y_i)$ and has an effective sensing radius of $r_i$ which can detect any person who is strictly within the radius of $r_i$ from $(x_i, y_i)$. In other words, the $i^{th}$ sensor can detect a person at location $(x_a, y_a)$ if and only if the Euclidean distance of $(x_i, y_i)$ and $(x_a, y_a)$ is strictly less than $r_i$. It is also known that the Euclidean distance of any two sensors $i$ and $j$ is strictly larger than $r_i + r_j$. Note that the Euclidean distance of two points, $(x_a, y_a)$ and $(x_b, y_b)$, is $\sqrt{|x_a - x_b|^2 + |y_a - y_b|^2}$.

Allen begins his infiltration mission at location $(x_s, y_s)$, and his target is located at $(x_t, y_t)$. Allen has the power to run extremely fast in a straight line while he needs to spend extra time to change his running trajectory (to adjust his footing). Although he is a fast runner, he still needs to make sure that none of the sensors detect him while he is running, i.e. there is no point in his running trajectory which is strictly within a sensor effective sensing radius.

Let $P = {(x_{p_1}, y_{p_1}), \dots, (x_{p_{|P|}}, y_{p_{|P|}})}$ be the set of locations where Allen changes his running trajectory, thus, Allen's running trajectory with $P$ is $(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)$ where $(x_a,y_a) \rightarrow (x_b,y_b)$ implies that Allen is running from $(x_a,y_a)$ to $(x_b,y_b)$ in a straight line. The set $P$ is feasible if and only if with $P$, Allen is not detected by any sensor and is not running out of the secret base (although, Allen is allowed to run along the secret base perimeter). Note that $x_p$ and $y_p$, $(x_p,y_p) \in P$, are not necessarily integers; they can be real numbers.

Your task in this problem is to find any one feasible $P$ which contains no more than $1000$ points.

艾伦是一名政府秘密特工，被指派潜入一个黑手党秘密基地，以获取有关该黑手党组织运作的关键情报。

该秘密基地是一个矩形区域，其四个顶点在笛卡尔坐标系中分别为 $(x_L,y_L)$、$(x_L,y_R)$、$(x_R,y_L)$ 和 $(x_R,y_R)$，其中 $x_L \lt x_R$ 且 $y_L \lt y_R$。基地内部共部署了 $N$ 个传感器。第 $i$ 个传感器位于 $(x_i, y_i)$，其有效感知半径为 $r_i$，可探测到严格位于以 $(x_i, y_i)$ 为中心、半径为 $r_i$ 的开圆盘内的任何人。换言之，当且仅当点 $(x_i, y_i)$ 与 $(x_a, y_a)$ 之间的欧几里得距离严格小于 $r_i$ 时，第 $i$ 个传感器才能探测到位于 $(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|}})\}$ 表示艾伦改变运动轨迹的位置集合，则其完整运动路径为

$$(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)$ 表示艾伦沿直线从 $(x_a,y_a)$ 奔跑至 $(x_b,y_b)$。集合 $P$ 是可行的，当且仅当：采用该路径时，艾伦既未被任何传感器探测到，也未跑出秘密基地边界（但允许沿基地周界边缘奔跑）。注意：对任意 $(x_p,y_p) \in P$，其坐标 $x_p$ 与 $y_p$ 不必为整数，可以是任意实数。

本题要求：找出任意一个可行的 $P$，且满足 $|P| \le 1000$。

Input begins with a line containing five integers: $N$ $x_L$ $y_L$ $x_R$ $y_R$ ($0 \le N \le 50$; $0 \le x_L \lt x_R \le 1000$; $0 \le y_L \lt y_R \le 1000$) representing the number of sensors and the secret base ($x_L$, $y_L$, $x_R$, $y_R$), respectively. The next line contains two integers: $x_s$ $y_s$ ($x_L \lt x_s \lt x_R$; $y_L \lt y_s \lt y_R$) representing Allen's initial location. The next line contains two integers: $x_t$ $y_t$ ($x_L \lt x_t \lt x_R$; $y_L \lt y_t \lt y_R$) representing Allen's target location. It is guaranteed that $x_s \ne x_t$ or $y_s \ne y_t$. The next $N$ lines each contains three integers: $x_i$ $y_i$ $r_i$ ($x_L \lt x_i - r_i \lt x_i + r_i \lt x_R$; $y_L \lt y_i - r_i \lt y_i + r_i \lt y_R$; $1 \le r_i \le 1000$) representing a sensor at location $(x_i, y_i)$ with an effective sensing radius of $r_i$. It is guaranteed that the Euclidean distance of any two sensors $i$ and $j$ is larger than $r_i + r_j$. It is also guaranteed that the Euclidean distance of $(x_s,y_s)$ and $(x_t,y_t)$ to any sensor $i$ is larger than $r_i$.

输入的第一行包含五个整数：$N$ $x_L$ $y_L$ $x_R$ $y_R$（其中 $0 \le N \le 50$；$0 \le x_L \lt x_R \le 1000$；$0 \le y_L \lt y_R \le 1000$），分别表示传感器的数量以及秘密基地的边界坐标 $(x_L, y_L, x_R, y_R)$。
第二行包含两个整数：$x_s$ $y_s$（满足 $x_L \lt x_s \lt x_R$ 且 $y_L \lt y_s \lt y_R$），表示艾伦的初始位置。
第三行包含两个整数：$x_t$ $y_t$（满足 $x_L \lt x_t \lt x_R$ 且 $y_L \lt y_t \lt y_R$），表示艾伦的目标位置。
保证 $x_s \ne x_t$ 或 $y_s \ne y_t$。
接下来的 $N$ 行，每行包含三个整数：$x_i$ $y_i$ $r_i$（满足 $x_L \lt x_i - r_i \lt x_i + r_i \lt x_R$；$y_L \lt y_i - r_i \lt y_i + r_i \lt 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$。

Output in a line an integer representing the size of a feasible $P$. The next $|P|$ lines each contains two real numbers (separated by a single space); the $j^{th}$ line contains $x_j$ $y_j$ representing the $j^{th}$ point in $P$. You may output any feasible $P$ with no more than $1000$ points.

Due to the nature of the output (floating point), let us define an epsilon $\epsilon$ to be $10^{-6}$ to verify the output. Consider $Q_1 = (x_s, y_s)$, $Q_{j+1} = P_j$ for all $1 \le j \le |P|$, and $Q_{|P|+2} = (x_t, y_t)$. Then, $P$ is considered correct if and only if $P$ contains no more than $1000$ points and all of the following are satisfied:

• $x_L - \epsilon \le x_{p_k} \le x_R + \epsilon$ and $y_L - \epsilon \le y_{p_k} \le y_R + \epsilon$ for all $1 \le k \le |P|$ (Allen is not running out of the secret base).
• For all $1 \le k \lt |Q|$, let $S_k$ be the line segment connecting $Q_k$ and $Q_{k+1}$ (Allen is running in straight line). For all $1 \le i \le N$, let $(x_{k,i},y_{k,i})$ be the point along $S_k$ that is the closest to the $i^{th}$ sensor's location, $(x_i,y_i)$. Let $d_{k,i}$ be the Euclidean distance between $(x_{k,i},y_{k,i})$ and $(x_i,y_i)$. Then, the constraint $r_i \le d_{k,i} + \epsilon$ should be satisfied (Allen is not detected by any sensor).
• All points in $Q$ are distinct. Two points, $(x_a,y_a)$ and $(x_b,y_b)$, are considered distinct if and only if $|x_a - x_b| \gt \epsilon$ or $|y_a - y_b| \gt \epsilon$.

在一行中输出一个整数，表示可行解 $P$ 的大小（即点的数量）。接下来的 $|P|$ 行每行包含两个实数（以单个空格分隔）；第 $j$ 行包含 $x_j$ 和 $y_j$，表示 $P$ 中的第 $j$ 个点。你可以输出任意一个满足条件的 $P$，且其点数不超过 $1000$。

由于输出涉及浮点数，我们定义容差 $\epsilon = 10^{-6}$ 用于验证输出正确性。令 $Q_1 = (x_s, y_s)$，对所有 $1 \le j \le |P|$ 有 $Q_{j+1} = P_j$，且 $Q_{|P|+2} = (x_t, y_t)$。则 $P$ 被视为正确当且仅当：$P$ 所含点数不超过 $1000$，且以下所有条件均满足：

• 对所有 $1 \le k \le |P|$，满足 $x_L - \epsilon \le x_{p_k} \le x_R + \epsilon$ 且 $y_L - \epsilon \le y_{p_k} \le y_R + \epsilon$（Allen 未跑出秘密基地边界）。
• 对所有 $1 \le k < |Q|$，令 $S_k$ 为连接 $Q_k$ 与 $Q_{k+1}$ 的线段（Allen 沿直线奔跑）。对所有 $1 \le i \le N$，令 $(x_{k,i},y_{k,i})$ 为线段 $S_k$ 上距离第 $i$ 个传感器位置 $(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,y_a)$ 与 $(x_b,y_b)$ 被视为互异当且仅当 $|x_a - x_b| > \epsilon$ 或 $|y_a - y_b| > \epsilon$。

Explanation for the sample input/output #1

The figure above shows the $P$ from the sample output. Note that there exists a feasible $P$ with only one point in this sample, although you are not required to find such $P$.

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

上图展示了样例输出中的集合 $P$。注意：在该样例中，存在一个仅含一个点的可行集合 $P$，但你无需找出这样的 $P$。