PTT數位生活區 / C_and_CPP (C/C++)

[ACM ] #11626 - Convex Hull

看板C_and_CPP (C/C++)作者 (Going under)時間16年前 (2009/09/15 01:00), 編輯推噓2(2推 0噓 6→)
留言8則, 2人參與, 最新討論串1/1
題目連結: http://0rz.tw/1M9JT 簡單介紹一下這題，題目中，inputs已經給了convex hull的解了，也就是 polygon of convex hull的每個點，然後題目要求依"逆時針"順序輸出這些 點。 一開始想說寫個compare function丟進去qsort()這題就結束了，不過事情 似乎沒有我這個憨人想得這麼單純..= =a。我目前想到的方法是參考自這個 http://www.geocities.com/kfzhouy/Hull.html，不過這麼做似乎又要跑一 次convex hull的流程，感覺既然題目已經給解答了，是不是沒這麼麻煩? 看看板友有沒有什麼想法開示一下小弟，先謝謝了！ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.40.118.113
推
09/15 01:21, , 1F
照x的值從左到右把點排序　然後決定起始點P
09/15 01:21, 1F
→
09/15 01:21, , 2F
把排序過的點掃一遍　比P低的照順序丟進lower_array
09/15 01:21, 2F
→
09/15 01:22, , 3F
比P高的(y值比較大的)丟進upper_array
09/15 01:22, 3F
→
09/15 01:22, , 4F
最後按照P -> lower_array -> 反向的upper_array印出來
09/15 01:22, 4F
→
09/15 01:23, , 5F
演算法大致是這樣　題目陷阱自己小心注意
09/15 01:23, 5F
→
09/15 04:41, , 6F
謝謝h大! 很簡單易懂的方法:D
09/15 04:41, 6F
→
09/15 04:42, , 7F
不過不知道為什麼還是吃WA..orz
09/15 04:42, 7F
推
09/15 10:11, , 8F
注意upper_array最右邊的點y值可能會相等的情況..
09/15 10:11, 8F
‣ 更多 Rukawa31 的文章
文章代碼(AID): #1AhdQXIh (C_and_CPP)
C_and_CPP 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 Rukawa31 的文章
文章代碼(AID): #1AhdQXIh (C_and_CPP)