看板ACMCLUB
标 题Re: world final problem A
发信站批踢踢兔 (Fri Apr 8 12:59:55 2005)
转信站ptt!Group.NCTU!grouppost!Group.NCTU!ptt2
※ 引述《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