[ACM ] 675

[DJWS (...)]

題號：

UVa 675 http://uva.onlinejudge.org/external/6/675.html

遇到的問題：

問題大意是：給定多邊形頂點座標，求出Convex Hull。
想請教大家我少考慮了哪些東西，導致WA。

有問題的code： (請善用置底文的標色功能)

http://nopaste.csie.org/c5b10

我使用的是Andrew's Monotone Chain演算法。演算法來源：
http://www.algorithmist.com/index.php/Monotone_Chain_Convex_Hull

補充說明：

給定的點當中，有些點的座標會一樣。我想我的程式碼應該可以處理這種情況才對。

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 220.137.112.12
推 ledia:我試一下, 三組測資, 最後一組的後面沒空行的話, 不會被處理
推 tkcn:如果hull上3點共線，程式會輸出中間那點，但題目沒定義清楚?
→ tkcn:請不要理會上面那行，我看錯了，程式不會輸出中間那點
→ tkcn:使用此演算法 AC 了，除了 1F 說的以外我沒看到其他錯誤。
→ DJWS:http://nopaste.csie.org/64e44 我把break往下搬，仍然是WA
→ DJWS:這樣改應該是可以的吧? 還是我腦子裡鬼打牆了...
→ tkcn:我的 C/C++ 語法不太行，所以沒辦法  Q_Q
→ DJWS:感謝大家...終於看出是哪裡錯了！
→ DJWS:錯在沒有確實找到多邊形第一個屬於convex hull的點
→ tkcn:原來如此！