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