题目描述

政府特工 Allen 接到任务，需要潜入一个黑手党秘密基地，获取有关其行动的重要信息。

秘密基地是笛卡尔坐标系中的一个矩形，其四个顶点为：

$$(x_L,y_L),\quad(x_L,y_R),\quad(x_R,y_L),\quad(x_R,y_R),$$

其中：

$$x_L<x_R,\qquad y_L<y_R.$$

基地内部放置了 $N$ 个传感器。

第 $i$ 个传感器位于 $(x_i,y_i)$，有效探测半径为 $r_i$。当且仅当某个位置 $(x_a,y_a)$ 与传感器中心的欧氏距离严格小于 $r_i$ 时，传感器能够发现该位置的人。

任意两个传感器 $i,j$ 之间的距离都严格大于：

$$r_i+r_j.$$

因此，所有传感器的有效探测圆盘两两分离。

Allen 从 $(x_s,y_s)$ 出发，目标地点为 $(x_t,y_t)$。

Allen 可以沿直线高速奔跑，但每次改变运动方向都需要额外时间。无论如何，他必须保证奔跑轨迹中的任何一点都不严格位于任意传感器的探测半径内。

设

$$P= \{(x_{p_1},y_{p_1}),\ldots,(x_{p_{|P|}},y_{p_{|P|}})\}$$

为 Allen 改变奔跑方向的位置序列。

对应的完整轨迹为：

$$(x_s,y_s) \rightarrow(x_{p_1},y_{p_1}) \rightarrow\cdots \rightarrow(x_{p_{|P|}},y_{p_{|P|}}) \rightarrow(x_t,y_t).$$

每一段轨迹都是连接相邻两个点的直线段。

如果满足以下条件，则称 $P$ 是可行的：

1. Allen 的整条轨迹都位于秘密基地内部或边界上；
2. 轨迹不进入任何传感器探测圆盘的内部。

中间点坐标不要求为整数，可以是实数。

请输出任意一个可行的 $P$，并保证：

$$|P|\le1000.$$

输入格式

第一行包含五个整数：

N xL yL xR yR

其中：

$$0\le N\le50,$$ $$0\le x_L<x_R\le1000,$$ $$0\le y_L<y_R\le1000.$$

第二行包含两个整数 $x_s,y_s$，表示起点，满足：

$$x_L<x_s<x_R,\qquad y_L<y_s<y_R.$$

第三行包含两个整数 $x_t,y_t$，表示终点，满足：

$$x_L<x_t<x_R,\qquad y_L<y_t<y_R.$$

保证起点与终点不同。

接下来 $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\le1000.$$

保证任意两个传感器圆盘之间没有接触或重叠，并且起点和终点到任意传感器中心的距离都严格大于对应半径。

输出格式

第一行输出一个整数 $|P|$，表示中间转向点的数量。

接下来 $|P|$ 行，每行输出两个实数 $x_j,y_j$，表示第 $j$ 个转向点。

你可以输出任意合法方案，但中间点数不得超过 $1000$。

判定规则

令：

$$\epsilon=10^{-6}.$$

定义：

$$Q_1=(x_s,y_s),$$ $$Q_{j+1}=P_j\quad(1\le j\le|P|),$$ $$Q_{|P|+2}=(x_t,y_t).$$

输出被认为正确，当且仅当满足以下全部条件。

1. 中间点位于基地范围内

对每个 $P_k=(x_{p_k},y_{p_k})$：

$$x_L-\epsilon\le x_{p_k}\le x_R+\epsilon,$$ $$y_L-\epsilon\le y_{p_k}\le y_R+\epsilon.$$

2. 每一段轨迹均避开传感器内部

对每个相邻点对 $Q_k,Q_{k+1}$，设线段为 $S_k$。

对于每个传感器 $i$，设线段 $S_k$ 上距离传感器中心 $(x_i,y_i)$ 最近的点为 $(x_{k,i},y_{k,i})$，对应距离为 $d_{k,i}$。

必须满足：

$$r_i\le d_{k,i}+\epsilon.$$

3. 所有轨迹点两两不同

对任意两个轨迹点 $(x_a,y_a)$ 与 $(x_b,y_b)$，必须有：

$$|x_a-x_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

一种合法输出

2
13.25 23.1234567
36.591003 7.1

图示

样例输出对应的路径

该样例实际上存在只使用一个中间点的可行方案，但题目并不要求最小化中间点数量。

样例 2

输入

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

一种合法输出

0