很感動, 搞了幾天終於過了
開始有信心做其它 sweep line 題
詳細算法在 kn 的 blog 有, 都是 sort by angle + sweep line
不同的是我用的是 heap
開頭以為可以用 stl priority_queue, 但在處理 delete 時, 不能像以前 expire + reach top 才 pop, 因為只是存在在 heap 中就會打亂次序
所以只好人手寫一個 heap
在發現無數的 bug (例如離散角度時沒有處理 -PI 和 PI 同時存在等等) 後, 加上無限的 WA, 終於過掉了!
之後再把無用的 code 刪掉, 竟然可以 runtime 第一
雖然其實沒有甚麼大不了, 但還是興奮了一陣子
No comments:
Post a Comment