切換
舊版
前往
大廳
主題

ZeroJudge - a191: 在世界遙遠的彼方 解題心得

Not In My Back Yard | 2019-04-06 20:54:38 | 巴幣 0 | 人氣 335

題目連結:


題目大意:
給定一正整數 N (1 ≦ N ≦ 10, 000),代表一標準座標平面上有 N 個點。接著的 N 列輸入便給定這 N 個點的 x 、 y 座標,每個點的 x 、 y 座標佔一列。

求對於每個點(按照給定的順序),與其他點的中最遠的距離之平方。



範例輸入:
12
2 1
3 1
1 2
2 2
3 2
4 2
1 3
2 3
3 3
4 3
2 4
3 4


範例輸出:
10
10
10
5
5
10
10
5
5
10
10
10


解題思維:
直接窮舉可以過,可是瀕臨時限範圍。但是窮舉的時候不能列舉到重覆的,不然必定超時。

而這題在對每個點找最遠的點之距離時,可以看到離當前點最遠的必定在這些點的凸包上(Convex Hull,定義見維基)。所以對於每個點只要窮舉與凸包上的點之距離即可。

而凸包的做法可以參見這位大大的演算法筆記網頁。

(2021 / 09 / 04 更新敘述)
該演算法的精神是先將所有點按照 X 軸小到大排序,再按照 Y 軸由小到大排序。這樣子第一個點將會是最「左下」的點。而且可以看到最「左下」的點必定在凸包裡,因此一開始先將其加入凸包中。

接著想像一條隱形的掃描線從最左側的點掃到最右側,之後每次碰到一個新的點 X 就預先與凸包最後加入的那一個點 Y 連線看看。此時如果凸包中有倒數第二加入的點 Z,則我們可以利用外積(Cross Product)來判斷邊 XY 跟邊 YZ 是呈順時針方向還是逆時針方向。

如果邊 YZ 相對於邊 XY 是呈現順時針方向(甚至是 X 、 Y 、 Z 共線),則代表 Y 這個點將會處於邊 ZX 的「內部」。也就代表著 Y 不應為凸包的一個頂點,因此將其移除;反之如果方向是逆時針則沒事。

示意圖如下:

因此掃到最右側之後便可以得出上半部的凸包。而下半部只要從最右側掃回到最左側,然後仿照原本上半的作法即可。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作