b370: 平面最小生成樹
Tags : Delaunay EMST 三角化 妮可 計算幾何
Accepted rate : 7人/16人 ( 44% ) [非即時]
評分方式:
Tolerant

最近更新 : 2016-07-06 11:27

Content

 

「不懂得溫暖為何物的人,只會單純地慢慢凍死。嘗過溫暖滋味的人,則會懷抱著『自己很冷』的意識逐漸死去,所以心境是更加不幸的。你聽懂了嗎?你很不幸。如果那時能死在后巷里,你還算幸福的。你應該明白現在的自己有多不幸。」-魔女之家

某 M 想到曾經也過得那充滿溫暖的日子,細數到底又隔了多少年,不禁眼泛淚光。

小夥伴去哪找呢?到底為何奮鬥?在那孤冷的夜晚下,敲著充滿污漬的鍵盤、做著 OJ 題目、模仿前人的足跡、記下自己的過錯。不外乎看到自己的愚笨,「不想輸」成為某 M 唯一的生存意志,花費數日時間解決一個簡單的問題,而別人早就理解這些前往下一個目標,逐漸地彼此距離越差越大,某 M 也只是身為一個即將被淘汰物種活著。

一開始就是錯的,只是隨著成長體現到錯誤的存在,某 M 意識到自己再不離開這裡,就會崩潰壞掉。也許曾經受到期待,在那社會包裝下,軀殼早已空洞。想著高中那年,一個人在研究室天馬行空地寫著代碼的日子,最小生成樹又是隔了多久才理解?LCS 又是真的在高中時明白?意識到自己說不定到現在都還沒明白,起碼在這個時候,寫一段最小生成樹吧!作為餞別。

Problem

給 N 個平面點,連接任兩個點 (x, y), (a, b) 的成本等同於兩個點的歐基里德距離 hypot(x-a, y-b),求最小生成樹的最小成本為何。

 

Input

輸入有多組測資,每一組第一行會有一個整數 N,表示接下來會有 N 個平面點。

接下來會有 N 行,第 i 行上會有兩個整數 x, y,表示第 i 個點座位於 (x, y)。

(N < 32767, 0 <= x, y <= 100,000)

每組測資,保證座標不會重複。

Output

對於每一組測資,輸出一行四捨五入到整數的最小生成樹成本。

Sample Input
2
1 1
2 2

4
3 4
4 0
4 3
0 0
Sample Output
1
8
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (10%): 1.0s , <1M
公開 測資點#1 (10%): 1.0s , <1M
公開 測資點#2 (10%): 1.0s , <1M
公開 測資點#3 (10%): 2.0s , <1M
公開 測資點#4 (10%): 1.0s , <1M
公開 測資點#5 (10%): 1.0s , <1M
公開 測資點#6 (10%): 2.0s , <1M
公開 測資點#7 (10%): 2.0s , <1M
公開 測資點#8 (10%): 2.0s , <1M
公開 測資點#9 (10%): 2.0s , <1M
Hint :

單筆測資點的總點數不超過 100,000。

如有出題重複、測資浮點數誤差問題,歡迎來信告知。

Tags:
Delaunay EMST 三角化 妮可 計算幾何
出處:
妮可 [管理者:
morris1028 (碼畜)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」