Minimizing the Maximum Distance to a Line

Given n points in the plane \(v_i(x_i,y_i)\), find the minimum possible value of \(D(l)=\max_{1\le i\le n}\,\mathrm{dis}(v_i,l)\) where \(l\) is an arbitrary line in the plane and \(\mathrm{dis}(v_i,l)\) represents the distance from point \(v_i\) to line \(l\).

Note that for any fixed line \(l\), if we project all points onto a direction perpendicular to \(l\), and denote the minimum and maximum projections as \(m\) and \(M\) respectively, then by choosing a line parallel to \(l\) passing through \((m+M)/2\), the maximum distance from the points to that line becomes \((M-m)/2\). Therefore, the problem is equivalent to finding the orientation (i.e. a unit normal vector) that minimizes \(\frac{1}{2}(M-m)\), which corresponds to half the minimum width of the set of points.

This problem can be solved by computing the convex hull of the set of points and then using the rotating calipers technique to compute the minimum width of the convex polygon. If the points are collinear (or if \(n<3\)), the answer is \(0\).

inputFormat

The first line contains an integer \(n\) (the number of points). Each of the following \(n\) lines contains two space-separated numbers \(x_i\) and \(y_i\), representing the coordinates of the \(i\)-th point.

outputFormat

Output a single number: the minimum possible value of \(D(l)\) (printed with at least 6 digits after the decimal point).

sample

3
0 0
1 0
0 1

0.353553