Problem L
Road to Rome

Archaeologists have recently discovered a site believed to be part of the Roman road system dating back to 450 BCE. They unearthed a scattered set of rectangular blocks of rock and seek your help to predict the direction of the road.

The most likely direction of the road is determined by identifying two parallel lines that enclose all the discovered rocks. Among all such pairs of parallel lines, your goal is to find the pair with the minimum perpendicular distance between them. If multiple pairs of parallel lines have the same minimum distance, any such pair is acceptable.

Specifically, you are given a set $S$ of $N$ distinct two-dimensional points representing the positions of the unearthed blocks. Each rectangular block is represented by a single point. Your task is to compute the perpendicular distance between the closest pair of parallel lines such that all blocks are enclosed (a block is considered enclosed if it lies on or between the two lines).

Input

• The first line contains a single integer $N$ ($5 \le N \le 10^6$) — the number of blocks.

• Each of the next $N$ lines contains two integers $x$ and $y$ ($-10^7 \le x, y \le 10^7$), representing the coordinates of a distinct block. All points are distinct; that is, for any two blocks $b_i = (x_i, y_i)$ and $b_j = (x_j, y_j)$ with $i \neq j$, either $x_i \neq x_j$ or $y_i \neq y_j$.

Output

Output a single line containing the minimum perpendicular distance between the two closest parallel lines that enclose all the blocks.

Your solution will be considered correct if the absolute error between your computed distance and the true minimum distance is less than $10^{-4}$.

11
-4 -8
-8 1
2 1
1 -3
-8 -9
-1 -3
1 9
4 4
-10 -1
-1 -9
4 2

11.503722

15
-17 79
-51 -52
14 20
-41 -77
-47 -78
-12 39
-93 81
-39 28
-62 -46
12 -22
-54 61
-91 72
2 -56
-7 -68
23 -57

89.555445