404387: GYM101492 D Geographic Information System

Geographic Information Systems (SIGs, in Portuguese) are becoming more and more important and useful in our lives. These systems are used in countries' national defense systems, for the analysis of public health data, in archaeology, and even in climate studies. In China, these systems are changing the way companies analyze and plan their business strategies. This development comes together with a bigger investment in R&D related to such technology. For this reason, the Chinese Association of Geographic Information Systems (ACSIG, in Portuguese) wants to attract students to work on projects related to this technology.

ACSIG knows that, in 2018, the brightest young minds in the planet will travel to Beijing to compete in the ACM ICPC World Finals. Given this event's reputation, ACSIG wants to recruit some of these contestants to be part of future projects. Now they are planning the problems they will use in their recruiting process. One of these problems is as follows.

Given the map of a certain geographic region and the subdivision of this region into sub-regions, we want to find a rectangle that contains in its interior all the points that define the subdivision. Now let's define the problem more formally. Consider that the map is the usual Cartesian plane, and the subdivision is given by a set of N straight lines. We want to find the rectangle with axis-aligned sides with the smallest area, and which contains all the vertices of the subdivision (the intersection points of the set of lines). Consider that the points in the boundary of the rectangle are also part of its interior.

ACSIG would like to test your knowledge, and asked you to solve this problem.

The first line contains an integer, N, the number of straight lines that define the subdivision. The i-th of the next N lines contains two real numbers, m_i, and b_i. These numbers represent the straight line m_ix - b_i. It is guaranteed that at least one pair of these lines intersect.

• 1 ≤ N ≤ 10⁵
• 0 < |m_i| ≤ 10⁷
• 0 ≤ |b_i| ≤ 10⁷

Print a line containing four real numbers , where are the coordinates of the bottom left vertex of the rectangle and (x_r, y_r) are the coordinates of the top right vertex. Absolute or relative errors of up to 10^- 4 are accepted.

2
0.444444 -9.0000
-0.125 -11.0000

3.51220 10.56098 3.51220 10.56098

5
-0.4444 -9.0000
-0.1250 -11.0000
0.5000 -7.0000
-0.5000 -2.0000
-0.2000 -5.0000

-125.89928 1.72668 16.36661 64.94964

6
3 5
3 9
3 15
3 19
-2 3
-2 -6

0.40000 -9.40000 5.00000 1.60000