Garden

Time limit2sMemory limit128 MB

Summary

Given n points, find the axis-aligned square of minimum side length that covers at least half the points, allowing real coordinates and boundary inclusion.

Level: Hard8 of 10
Topics: Binary search, Geometry, Sliding window
Solved: No attempts yet

Problem

There are n plants in a garden. Each plant has an x and y coordinate on the plane.

Find an axis-aligned square plot that contains at least half of all plants, that is, at least ceil(n / 2) plants. Plants on the boundary of the square are counted as included.

Among all such squares, find one with the smallest side length. If there are multiple valid answers, you may output any one of them.

Input

The first line contains the number of plants n. (4 <= n <= 1,000)

Each of the next n lines contains the coordinates x y of one plant. Each coordinate is a positive real number at most 100,015 and may be given with up to six digits after the decimal point.

Output

On the first line, output the side length of the smallest square that satisfies the condition.

On the second line, output the coordinates of the lower-left corner of that square.

If there are multiple valid answers, output any one of them. A relative error up to 10^-6 is allowed.

Examples1

Example 1
Input
```
4
1.23 4.14
6.02 3
5 6
10 4.5
```
Expected output
```
3.0
4 3
```