• [1362] 最短路线

  • 时间限制: 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
  • 操作

显示春菜