創作內容

0 GP

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

作者:Not In My Back Yard│2019-04-06 20:54:38│巴幣:0│人氣:132
題目連結:


題目大意:
給定一正整數 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,定義見維基)。所以對於每個點只要窮舉與凸包上的點之距離即可。

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

本人採取的作法是將點先對 x 由小到大排序,再對 y 由小到大排序。然後由 x 最小到最大的點(從最左到最右)掃過一次,生出一個一半的凸包(下凸包);之後,反方向掃回來生成上凸包。

途中,對於每個新掃到的點跟前面的點作叉積(Cross Product),判斷是否是以逆時針旋轉,也就是叉積之值大於 0 。因為從最左邊找凸包的話,凸包的成長應為逆時針旋轉,而不是順時針旋轉。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。
引用網址:https://home.gamer.com.tw/TrackBack.php?sn=4350466
All rights reserved. 版權所有,保留一切權利

相關創作

同標籤作品搜尋:程式題目解題心得|數學|幾何|窮舉

留言共 0 篇留言

我要留言提醒:您尚未登入,請先登入再留言

喜歡★inversion 可決定是否刪除您的留言,請勿發表違反站規文字。

前一篇:ZeroJudge - ... 後一篇:ZeroJudge - ...

追蹤私訊切換新版閱覽

作品資料夾

lucky74181大家
《我好像喜歡上妳了》❤❤睡前音樂:Kaari - Fall In Love🎵❤🎵看更多我要大聲說昨天20:20


face基於日前微軟官方表示 Internet Explorer 不再支援新的網路標準,可能無法使用新的應用程式來呈現網站內容,在瀏覽器支援度及網站安全性的雙重考量下,為了讓巴友們有更好的使用體驗,巴哈姆特即將於 2019年9月2日 停止支援 Internet Explorer 瀏覽器的頁面呈現和功能。
屆時建議您使用下述瀏覽器來瀏覽巴哈姆特:
。Google Chrome(推薦)
。Mozilla Firefox
。Microsoft Edge(Windows10以上的作業系統版本才可使用)

face我們了解您不想看到廣告的心情⋯ 若您願意支持巴哈姆特永續經營,請將 gamer.com.tw 加入廣告阻擋工具的白名單中,謝謝 !【教學】