※ 引述《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