「不懂得溫暖為何物的人,只會單純地慢慢凍死。嘗過溫暖滋味的人,則會懷抱著『自己很冷』的意識逐漸死去,所以心境是更加不幸的。你聽懂了嗎?你很不幸。如果那時能死在后巷里,你還算幸福的。你應該明白現在的自己有多不幸。」-魔女之家
某 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
單筆測資點的總點數不超過 100,000。
如有出題重複、測資浮點數誤差問題,歡迎來信告知。
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」
|