某岛

… : "…アッカリ～ン . .. . " .. .
September 26, 2011

UVaLive 3662. Another Minimum Spanning Tree

Brief description:

曼哈顿最小生成树问题 ( Minimum Spanning Tree)

Analysis:

。。。TC 上 bmerry 的教程写的比较详细，可以证明 8 每个象限内只有最近的点有可能在最小生成树中。。
之后是非常经典的坐标变换。。

完整代码）

External link:

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=242
http://acm.hust.edu.cn:8080/judge/problem/viewProblem.action?id=23379
http://hi.baidu.com/cloudygoose/blog/item/be300aed459c702b63d09fe9.html
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lineSweep

Posted by xiaodao
Category: 日常
Tags: ,

« | »

  • Archives

    open all | close all