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

[ACM ] 675

看板C_and_CPP (C/C++)作者 (...)時間16年前 (2010/04/07 23:13), 編輯推噓2(2推 0噓 8→)
留言10則, 3人參與, 最新討論串1/1
題號： 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
推
04/08 09:52, , 1F
我試一下, 三組測資, 最後一組的後面沒空行的話, 不會被處理
04/08 09:52, 1F
推
04/08 14:03, , 2F
如果hull上3點共線，程式會輸出中間那點，但題目沒定義清楚?
04/08 14:03, 2F
→
04/08 14:07, , 3F
請不要理會上面那行，我看錯了，程式不會輸出中間那點
04/08 14:07, 3F
→
04/08 15:16, , 4F
使用此演算法 AC 了，除了 1F 說的以外我沒看到其他錯誤。
04/08 15:16, 4F
→
04/08 16:26, , 5F
http://nopaste.csie.org/64e44 我把break往下搬，仍然是WA
04/08 16:26, 5F
→
04/08 16:29, , 6F
這樣改應該是可以的吧? 還是我腦子裡鬼打牆了...
04/08 16:29, 6F
→
04/08 17:10, , 7F
我的 C/C++ 語法不太行，所以沒辦法 Q_Q
04/08 17:10, 7F
→
04/08 17:30, , 8F
感謝大家...終於看出是哪裡錯了！
04/08 17:30, 8F
→
04/08 17:32, , 9F
錯在沒有確實找到多邊形第一個屬於convex hull的點
04/08 17:32, 9F
→
04/08 17:38, , 10F
原來如此！
04/08 17:38, 10F
‣ 更多 DJWS 的文章
文章代碼(AID): #1BlA4mrd (C_and_CPP)
C_and_CPP 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 DJWS 的文章
文章代碼(AID): #1BlA4mrd (C_and_CPP)