※ 引述《hil (隨機客)》之銘言：
: ※ 引述《sophialiege ()》之銘言：
: : 應該是要硬做吧
: : 關鍵在於他說至少有一個endpoint在兩個圖內
: : 可能存在tricky測資是endpoint在boundary上
: : 然後它是浮點數,可能要用string讀進來
: : 全部乘上1000
: : 用分數表示比例(比較用交叉相乘),應該用long long就不會overflow了
: 硬作所需的時間會不會太久?
: 這一題沒有任何一隊作出來, 有三隊試過, 其中U of Waterloo好像試了
: 九次都沒成功, 如果這題被他們做出來, 冠軍可能會換人.
這麼一說,
好像一遇到某一種測資就超時了......
如果有明確endpoint(就是不在boundary上的endpoint),時間複雜度是O(n^4)
但如果沒有任何明確endpoint,但endpoint很多時就必定超時
如:
(1)___________ (2)
___________
___________
___________
___________
不過能做到這種事的只有一組平行線段或者什麼都沒有,可能要當特例處理掉
--
※ 發信站: 批踢踢兔(ptt2.cc)
◆ From: 140.112.250.176