某島

… : "…アッカリ~ン . .. . " .. .
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