F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
大视野在线测评-欢迎您
[ New Thread ]
Problem 4235 >> 关于这题一些个人的想法
lichangdongtw @ 2018-01-10 07:43:02
[ Quote ] [ Edit ] [ Delete ] 1#
原矩形共有O(n+m)条斜线,反射会发生一定是光路上有障碍,反射方向与障碍两边是否有障碍有关,将起点视作一个障碍后,每个障碍会分裂出2条斜线,每次光线都会完整的走完一条斜线,故我们可以将每条斜线分成上下方向后,放进队列里bfs,总的状态数是O(n+m+k)的,每次反射后要二分出走进新的斜线分裂出的第几条线所以总复杂度是O((n+m+k)logk)
这个做法不是很好写....而且我感觉这题卡时卡空间.....就没写
想法仅供参考不确定正确性..
save_code @ 2018-08-23 02:02:23
[ Quote ] [ Edit ] [ Delete ] 2#
没这么简单,补充一点,需要减掉 交点个数, 扫描线算法,没跑。。。。
save_code @ 2018-08-23 02:13:45
[ Quote ] [ Edit ] [ Delete ] 3#
不是吧,没有减掉交点个数就A了。。。。这。。。对吗???
[Top] [Previous Page] [Next Page]

HOME Back