Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom4月前

04/19
21:47
Delaunay三角剖分 欧几里得最小距离生成树

[2017.04.18 省选模拟赛] 旅行商

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

前面说到moreD在天际里投机倒把赚钱,看着自己的金币蹭蹭往上涨当然是一件令人偷税愉悦(●’◡’●)的事情。
但是考虑到在路上跑的时间成本,整件事情就不那么让人满意了。
moreD共在 N 个城市间倒卖物品。他从 1 号城市出发,自然,这 N 个城市都是要访问到的。
好消息是,moreD装了一个奇怪的mod,可以让他使用飞行坐骑,于是两个城市间的距离就是它们之间的直线距离。
由于moreD玩游戏的时候是个没有耐心的人,他希望最小化在路上最长花费的时间,也就是说,使得在城市间飞行的距离的最大值最小。
moreD明白这应该需要写算法解决,但是由于3D眩晕症,他现在已经脸如死灰地躺在床上了(◎﹏◎),显然不能胜任这个任务。于是他希望你能帮他解决这个问题。
无畏的勇者(没有龙可以屠实在是不好意思了)啊,赶快解决这个问题,把moreD从无尽跑路的深渊中拯救出来吧!

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

第一行一个整数 N ,表示城市的数量。
接下来 N 行每行两个实数 X_iY_i ,表示第 i 个城市的坐标。注意两个实数之间可能由若干个空格隔开。

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

一个实数表示最大距离的最小值。你的答案被认为正确当且仅当与标准答案的绝对或相对误差不超过 10^{-6}

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

4
-3.71325669183 4.75409581640
-1.10008780877 -3.49106223682
0.74164638894 2.51398179707
2.06373891101 3.50472375085

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

6.28112559

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

对于 30\% 的数据,N\le500
对于另外 20\% 的数据,N\le5000 且点的空间分布大致均匀
对于 100\% 的数据,N\le50000

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

欧几里得最小距离生成树

可以用Delaunay三角剖分解决,求出三角剖分后生成树肯定是三角剖分的一个子集

证明和构造方法可以参考2006年王栋的集训队论文

 

[2017.04.18 省选模拟赛] 旅行商