「不懂得溫暖為何物的人，只會單純地慢慢凍死。嘗過溫暖滋味的人，則會懷抱著『自己很冷』的意識逐漸死去，所以心境是更加不幸的。你聽懂了嗎？你很不幸。如果那時能死在后巷里，你還算幸福的。你應該明白現在的自己有多不幸。」－魔女之家
某 M 想到曾經也過得那充滿溫暖的日子，細數到底又隔了多少年，不禁眼泛淚光。
小夥伴去哪找呢？到底為何奮鬥？在那孤冷的夜晚下，敲著充滿污漬的鍵盤、做著 OJ 題目、模仿前人的足跡、記下自己的過錯。不外乎看到自己的愚笨，「不想輸」成為某 M 唯一的生存意志，花費數日時間解決一個簡單的問題，而別人早就理解這些前往下一個目標，逐漸地彼此距離越差越大，某 M 也只是身為一個即將被淘汰物種活著。
一開始就是錯的，只是隨著成長體現到錯誤的存在，某 M 意識到自己再不離開這裡，就會崩潰壞掉。也許曾經受到期待，在那社會包裝下，軀殼早已空洞。想著高中那年，一個人在研究室天馬行空地寫著代碼的日子，最小生成樹又是隔了多久才理解？LCS 又是真的在高中時明白？意識到自己說不定到現在都還沒明白，起碼在這個時候，寫一段最小生成樹吧！作為餞別。
Problem
給 N 個平面點，連接任兩個點 (x, y), (a, b) 的成本等同於兩個點的歐基里德距離 hypot(x-a, y-b)，求最小生成樹的最小成本為何。
輸入有多組測資，每一組第一行會有一個整數 N，表示接下來會有 N 個平面點。
接下來會有 N 行，第 i 行上會有兩個整數 x, y，表示第 i 個點座位於 (x, y)。
(N < 32767, 0 <= x, y <= 100,000)
每組測資，保證座標不會重複。
對於每一組測資，輸出一行四捨五入到整數的最小生成樹成本。
2 1 1 2 2 4 3 4 4 0 4 3 0 0
1 8
公開 測資點#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
單筆測資點的總點數不超過 100,000。
如有出題重複、測資浮點數誤差問題，歡迎來信告知。
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||