Codah ClubУпражнявай. Изпращай. Напредвай.
Вход
Български
#00005B

z-skakac

Mr. Little Z and his best friend R2D2 love to play the following game:


First, R2D2 draws a few lines on the concrete. After that Mr. Little Z must jump from point A to point B without leaping over any of the lines R2D2 painted.


Since Mr. Little Z was always winning, R2D2 has decided to draw so many lines that Mr. Little Z must lose.


Mr. Little Z has decided to make a robot that will play in his place. After a few hard days of work, Mr. Little Z has made his robot, a robot that can jump as many times as he wants to. Unfortunately, Mr. Little Z couldn't write a program for the robot. Help Mr. Little z write a program for his robot.


For the given map that contains all the lines R2D2 drew, the program should find a path from point A to point B, such that the path doesn't cross any of the lines. The points on the path mustn't be outside of the given territory (the area covers 300x300 meters), but it can be on the edge of the territory.


InputThe first line of the standard input contains four real numbers: XStart, YStart, XEnd, YEnd representing the coordinates of the start position and the end position. Each of the numbers is in the segment [0.00, 300.00]. The second line contains a number M (M <= 300), which is the number of lines R2D2 has drawn. Each of the lines is SHORTER than 25 meters. Finally, in each of the next M lines you are given four real numbers X1, Y1, X2, Y2, corresponding to the start coordinates and end coordinates of the lines R2D2 has drawn.

OutputTo the standard output in the first line write the number N, where N is the number of jumps needed to get from the starting point to the end point. After that, in each of the next N-1 lines write 2 real numbers (with 2 decimals at most), representing the coordinates of the positions between the starting and end points. The solution must be <= 300 jumps.

Note: The solution is not unique!


Input:
0.00 0.00 10.00 10.00
1
5.00 0.00 5.00 10.00
Output:
2
0.00 11.00
Explanation: To get from the point (0.00, 0.00) to (10.00, 10.00) you need 2 jumps, the first jump to the point (0.00, 11.00), and then from that point to the end point. The correct solution can be like this, too:
Output:
3
0.00 5.00
0.00 11.00
Note: The jumper mustn't pass over the edge points of the lines R2D2 has drawn!

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.