• [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
  • 操作

显示春菜