Internet Problem Solving Contest

IPSC 2002

Problem G – Gardening

Banto and Santo inherited a Precious plant garden from their uncle Manto. The Precious plant is a very strange plant. It is one-dimensional, the only dimension being its height. Viewed from above it looks like a point. The garden is a square 50 by 50 meters. It has to be split into two parts. Santo (as he is very lazy) does not want to do the work so he told Banto: "Just split the garden, but make sure that my part is a square with its sides parallel to the sides of the original garden and that it contains at least half of the Precious plant trees." Banto agreed to do this but he added one condition: Santo's part must have the smallest area possible.

Banto measured positions of all Precious plant trees in the garden and typed them into the computer. Now he is trying to determine the smallest square that contains at least half of the Precious plant trees. A plant is contained in a square if it is inside it or on its border. It is not an easy problem. Go! Help him!

Input file specification

The input file contains the number of Precious plant trees on the first line. Each of the following lines contains two numbers specifying the position of a Precious plant. Coordinates are measured from the south-west corner of the garden, parallel to its sides, in meters, with infinite precision. All numbers in the file are distinct (this comes from a rule about growing Precious plants that we will not explain here).

Output file specification

The output file should contain two lines with two numbers each: coordinates of arbitrary two opposing corners of the minimal square containing at least half of the Precious plant trees.


Input file:
1.23 4.14
6.02 3
5 6
10 4.5
Output file: (out of several possibilities)
4 3
7 6