[D] 最短路线
- 时间限制: 1000 ms 内存限制: 65535 K
- 问题描述
-
从前有座山，山里有个城堡，城堡三面环山。城主为了防御敌人的入侵，所以在大道横向筑起了一道墙，这样一来就是个铜墙铁壁了，易守难攻。该墙是直线型的，没有弯曲的部分。但是，一旦有人入侵，军队应该快速赶到城墙防御敌人。所以，城主在城墙内又筑起一些军营。现在告诉你这些军营的坐标，那么如何建造城墙（你可以考虑城墙是无限延伸的），才能使所有军营到城墙的距离之和最短？
- 输入
-
输入第一行包括一个正整数 N(4 <= N <= 10000)，表示为军营的数量。
接下来N行，每行包括两个实数 x(-1000.00 <= x <= 1000.00)和 y(-1000.00 <= y <= 1000.00)，表示该军营的坐标（不会有两个军营在同一坐标上，且不会所有的点都在一直线上；军营在城墙上也是可以的）。
- 输出
-
输出一行为所有军营到城墙的距离之和的最小值，保留两位小数。
- 样例输入
-
4 0.00 0.00 1.00 1.00 0.00 1.00 1.00 0.00
- 样例输出
-
2.00
- 提示
-
Use scanf and printf instead of cin and cout.
- 来源
-
Hungar
- 操作
-
