Polygon

Special Judge Time Limit: 6000/3000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

      The Ministry of Defense of Flatland is planning to build a new polygon. The polygon must have a form of a perfect circle.
      However, generals in the Ministry are concerned about the security of the polygon. There are several special power shields above Flatland, each of them has a form of a rectangle with edges parallel to coordinate axes. The generals want to find such a place for the polygon, that there are two different power shields that completely cover the polygon.
      Of course, the generals want to build as large polygon as possible. Help them to find such position for the polygon that it has the greatest possible area.

Input

      The first line of the input file contains n — the number of the power shields (1 ≤ n ≤ 60 000). The following n lines describe shields — each shield is described with four integer numbers: xmin,ymin, xmax,ymax. All coordinates do not exceed 100 000 by their absolute values.

Output

      Output three real numbers — the coordinates of the center of the polygon to build and its radius. All numbers must be printed with exactly one digit after the decimal point. If it is impossible to build the polygon, print “Impossible” at the first line of the output file.

Sample Input

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

Sample Output

3.0 2.0 1.0
Impossible
1.5 1.5 1.5

Source

Andrew Stankevich Contest 21

Manager

Information
Solved Number13
Submit Number32
Problem Tags
data structures
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel