Problem
The Ministry of Road Transport has decided to build a new office for itself. Since the minister regularly goes out to inspect the most important routes, it was decided that the office of the ministry should not be located too far from them.
The most important alignments are straight lines on the plane. The Ministry wants to choose a location for its office so that the maximum distance from the office to the highways is as short as possible.
You need to write a program that, given the location of the most important highways, determines the optimal location of the house for the office of the Ministry of Road Transport.
Input
The first line of the input file contains a single integer n — number of most important traces (1 ≤ n ≤ 104 ).
The next n lines describe the traces. Each trace is described by four integers x1, y1, x2 and y2 and is a straight line passing through the points (x1, y1) and (x2, y2) . The coordinates of the given points do not exceed 104 in absolute value. Dots (x1 , y1) and (x2 , y2) do not match for any line.
Output
The output file should contain two space-separated real numbers: the coordinates of the point where the office of the Ministry of Road Transport should be built. Modulo coordinates must not exceed 109, it is guaranteed that at least one such answer exists. If there are several optimal answers, print any of them.
The answer must have an absolute or relative error of no more than 10−6, which means the following. Let the maximum distance from the drawn point to some trace be equal to x, and in the correct answer it is equal to y. The answer will be counted if the value of the expression | x .minus; y | / max(1, |y| ) does not exceed 10−6.
| Input |
Output |
|
4
0 0 0 1
0 0 1 0
1 1 2 1
1 1 1 2
|
0.5000000004656613 0.4999999995343387 |
|
7
376 -9811 376 -4207
6930 -3493 6930 -8337
1963 -251 1963 -5008
-1055 9990 -684 9990
3775 -348 3775 1336
7706 -2550 7706 -8412
-9589 8339 -4875 8339
|
4040.9996151750674 12003.999615175067 |
Personal Olympiad, All-Russian Olympiad for schoolchildren, Regional stage, 2011, 2nd day, Problem D