Airport
题意翻译
## 题目描述
平面上有$n$个点,求一条直线,使得这$n$个点都在这条直线上或同侧,且每个点到该直线的距离之和尽量小。
## 输入格式
第一行,数据组数$N$。
对于每组数据,第一行,点的个数$n$。之后$n$行,每行两个整数$x,y$,表示点的坐标。
## 输出格式
对于第$x$组数据,输出一行,先输出``Case #x: ``,之后输出每个点到该直线的距离之和$/n$,保留三位小数。
## 数据范围
对于所有数据,$N\leqslant 65$,$n\leqslant 10^4$,$|x|,|y|\leqslant 8*10^4$。
题目描述
[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=23&page=show_problem&problem=2109
[PDF](https://uva.onlinejudge.org/external/111/p11168.pdf)
![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA11168/f16065b7494be61f95712a581f99b12cd3a92342.png)
输入输出格式
输入格式
![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA11168/3a3768b6dc72c84bf7b5c738abc62e8367230f89.png)
输出格式
![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA11168/a28cb0782efcd96630186f88e9caa70aef8bc67a.png)
输入输出样例
输入样例 #1
4
4
0 0
0 1
1 0
1 1
2
15035 39572
34582 39535
3
0 0
0 1
1 0
5
0 0
0 2
2 0
2 2
1 1
输出样例 #1
Case #1: 0.500
Case #2: 0.000
Case #3: 0.236
Case #4: 1.000