Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

I. Mission Possible

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputAllen, 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 < x_R$$$ and $$$y_L < 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.

Input

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 < x_R \le 1000$$$; $$$0 \le y_L < 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 < x_s < x_R$$$; $$$y_L < y_s < y_R$$$) representing Allen's initial location. The next line contains two integers: $$$x_t$$$ $$$y_t$$$ ($$$x_L < x_t < x_R$$$; $$$y_L < y_t < 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 < 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$$$) 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$$$.

Output

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 < |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| > \epsilon$$$ or $$$|y_a - y_b| > \epsilon$$$.

Examples

Input

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

Output

2 13.25 23.1234567 36.591003 7.1

Input

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

Output

0

Note

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$$$.

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/11/2019 10:06:26 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|