All submissions for this problem are available.
The students are painting their imaginations on the canvas. One of the students Zetti likes only line segments and he has given a poster composed of only straight line segments to the authorities. But he has violated the frame dimensions asked for poster and has only the last few minutes to rectify this mistake. He knows that you are good at programming and has approached you for help.
The task for the problem is simple. You will be given a pair of points in the 2D plane representing the lower left(x1, y1) and the upper right(x2, y2) corners of the frame. There are N line segments and you know the coordinates of its end points. You need to print the end points of the maximum length segment that will be completely inside (or on the boundary) of the frame. If the line segment will always be outside the frame print “OUTSIDE” instead. Below is the graph of the sample test case. (Not to scale).
The first line of input consists of the number of test cases T. The description of T test cases follows. Each test case begins with five integers on a line x1 y1 x2 y2 N (all separated by single space). Then follows N lines each consisting of a four integers ax ay bx by denoting the end points of the line segment. It is guaranteed that the length of any line segment is greater than zero and the area of the frame is greater than 0.
For each test case T, you need to print N lines. Each line should contain the end points of the truncated line segment such that it is within (or on the boundary) of the frame. These end points must be sorted by its abscissa value and in case the x value of both points are same, then the ordinate value. If no part of the segment can be inside the frame the print “OUTSIDE”.
Note that the answers would be accepted only if it has an error of less than 10-6.
The absolute value of all given points is less than equal to 109
Input: 1 1 1 5 5 3 1 6 4 7 2 4 2 2 3 3 7 3 Output: OUTSIDE 2 2 2 4 3 3 5 3
See the image above for explanations.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, GO, PYP3|
Fetching successful submissions
If you are still having problems, see a sample solution here.