← 返回题目
题库练习 「SHOI2011」直线拟合
← 上一题 下一题 →

A5751 | 「SHOI2011」直线拟合

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

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

输入格式

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

输出格式

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

输入输出样例

输入 #1
6
1 0
2 0
3 0
3 2
4 0
5 0
输出 #1
1.00
输入 #2
6
-2 -1
-1 2
1 2
2 3
3 3
4 4
输出 #2
0.86
C++ 编辑器
输入
输出