读书人

区域最短路径有关问题

发布时间: 2012-09-02 21:00:34 作者: rapoo

区域最短路径问题
题目地址:
http://acm.nyist.net/JudgeOnline/problem.php?pid=7

这道题的难度是3,但是我怎么觉得很麻烦呢?最终的距离计算公式是
n个sqrt((x-x1)^2+(y-y2)^2)相加

那么用程序怎么解出x和y呢?
虚心求教!

在网上看了一篇对这个的分析:
http://www.cnblogs.com/mdyang/archive/2011/05/02/2034070.html

觉得说的是不正确的,因为按照这种方法,最终求出来的x和y的值都只能是输入数据中的值,而不会出现其他值。
烦请高手给个好的思路。

[解决办法]
怎么会,你将所有输入的x排序,取x的中位数X;将所有输入的y排序,取y的中位数Y;组成的(X,Y),应该就不一定是输入数据中的值了吧
[解决办法]
5
2 9
5 20
11 9
1 1
1 20
拿这组数据举例。、。。
[解决办法]
x:排序后为 1 1 2 5 11 他的中位数是X:(2+5)/2=3
y:排序后为 1 9 9 20 20 他的中位数是Y:(20+9)/2=14
所以,邮局在(3,14)

读书人网 >C语言

热点推荐