作者Rukawa31 (Going under)
看板C_and_CPP
標題[ACM ] #11626 - Convex Hull
時間Tue Sep 15 00:58:57 2009
題目連結:
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
1F：推 holymars:照x的值從左到右把點排序 然後決定起始點P 09/15 01:21
2F：→ holymars:把排序過的點掃一遍 比P低的照順序丟進lower_array 09/15 01:21
3F：→ holymars:比P高的(y值比較大的)丟進upper_array 09/15 01:22
4F：→ holymars:最後按照P -> lower_array -> 反向的upper_array印出來 09/15 01:22
5F：→ holymars:演算法大致是這樣 題目陷阱自己小心注意 09/15 01:23
6F：→ Rukawa31:謝謝h大! 很簡單易懂的方法:D 09/15 04:41
7F：→ Rukawa31:不過不知道為什麼還是吃WA..orz 09/15 04:42
8F：推 holymars:注意upper_array最右邊的點y值可能會相等的情況.. 09/15 10:11