提示: 欢迎访问OurACM平台。
Problem 1510 Oaiei's Trouble

Accept: 28    Submit: 112
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

Oaiei is a lazy boy. A semester will soon pass, but learning is never too late. Computer Graphics is a relatively easy subject, so he decides to go over this course first. 2D coordinate system is the basis of the graphics so let’s consider a simple problem on how to determine whether a point is in a rectangle, as shown below:

To determine whether a point P(x, y) is in a rectangle, we can simply test whether it meets the following inequality:

where xl and yb are coordinates of the lower-left corner of the rectangle, and xr and yt are coordinates of the upper-right corner of the rectangle. If the point P meets the inequality above, it is within the rectangle; otherwise, it’s outside the rectangle.

What about a line segment? It’s more or less the same. An arbitrary line segment, compared to a defined rectangle, all the possible relationships can be showed as follows:

Now it’s your question. In a 2D coordinate system, oaiei has drawn a rectangle. All he wants are lines in the rectangular region and the outside part is cut off. Can you help him find out the coordinates of the line after clipping?

Input

The input consists of several test cases. For each case, the first line consists of four integers xl, yb, xr, yt (0 <= xl, yb, xr, yt <= 100) separated by a space. The first two integers are the coordinates describing the lower-left corner of the rectangle. The latter two are the coordinates describing the upper-right corner of the rectangle. The second line consists of a integer N (N <= 100), indicating the number of lines oaiei has drawn. For line 3 to n + 2, each line consists of four integers sl, eb, sr, et (-1000 <= sl, eb, sr, et <= 1000, sl <= sr, eb <=et). The first two integers are the coordinates describing the lower-left corner of the line. The latter two are the coordinates describing the upper-right corner of the line.

Output

The first line should contain the number of lines after clipping. Then each line for a line segment which consists of four numbers. The first two are the coordinates describing the lower-left corner of the line. The latter two are the coordinates describing the upper-right corner of the line. All the number should be rounded to two decimal digits. If the lower-left point meets the upper-right point, output the two points. All output should be the same order as input.

Sample Input

0 0 2 2 4 0 0 1 1 -2 -1 3 3 1 2 1 4 3 3 4 4

Sample Output

3 0.00 0.00 1.00 1.00 0.00 0.60 1.75 2.00 1.00 2.00 1.00 2.00

Source

FOJ月赛-2007年6月

Submit  Back  Status  Discuss