#P4636. [SHOI2011] 直线拟合

[SHOI2011] 直线拟合

题目描述

平面上有 nn 个点 vi(xi,yi)v_i(x_i,y_i) 。求 D(l)=max1indis(vi,l)D(l)=\max_{1\le i\le n} dis(v_i,l) 的最小可能值,其中变量 ll 是平面上的一条直线,函数 dis(vi,l)dis(v_i,l) 表示直线 ll 与点 viv_i 之间的距离。

输入格式

输入的第一行为一个正整数 nn 。接下来 nn 行,每行一对整数 xi,yix_i , y_i​​ ,用一个空格分隔,依次表示这 nn 个点的坐标,其中 xi,yi108|x_i|,|y_i| \le 10^8 ,且不同的点不会重合。

输出格式

输出只有一行,包含一个实数,即 D(l)D(l) 的最小值,四舍五入到小数点后两位。

6
1 0
2 0
3 0
3 2
4 0
5 0
1.00
6
-2 -1
-1 2
1 2
2 3
3 3
4 4
0.86

提示

样例解释 1

样例 11 中, 取到最小值时的直线 lly=1y=1

样例解释 2

样例 22 中的 66 个点,以及 D(l)D(l) 取到最小值时的直线 ll 如图所示。

1

数据范围与提示

测试点 11n=3n=3

测试点 242 \sim 43n1003 \le n \le 100

测试点 575 \sim 7100<n100000100 < n \le 100000 ,且输入文件如下生成:选定一条线段,每次先在该线段上等概率随机选择一个点,再取离该点最近的整点。

测试点 8108 \sim 103<n1000003 < n \le 100000