A5751. 「SHOI2011」直线拟合
编程题
省选/NOI-
知识点
题目描述
平面上有 $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
说明/提示
| 数据编号 | 数据限制 |
| :--: | :-------------------: |
| 1 | $ n=3$ |
| 2~4 | $3 \le n\le 100$ |
| 5~7 | $100 < n\le 100000$ ，且输入文件如下生成：选定一条线段，每次先在该线段上等概率随机选择一个点，再取离该点最近的整点 |
| 8~10 | $3 < n\le 100000$ |
| :--: | :-------------------: |
| 1 | $ n=3$ |
| 2~4 | $3 \le n\le 100$ |
| 5~7 | $100 < n\le 100000$ ，且输入文件如下生成：选定一条线段，每次先在该线段上等概率随机选择一个点，再取离该点最近的整点 |
| 8~10 | $3 < n\le 100000$ |