直接说难点和注意事项:
开区间处理:窗户是开矩形,光线在边界上被吸收。代码中使用 X1 + EPS < X2 等严格不等式判断交集,确保边界点不会被错误计入。
浮点精度:使用 EPS = 1E-12 处理浮点比较,避免因精度问题导致的误判。
集合爆炸:每次迭代矩形数量可能增长,代码设置了 MAX_RECTS = 200000 作为上限,防止内存溢出。实际数据中矩形数量不会达到此上限。
反射次数上限:T_MAX = 2000 足以覆盖所有有效光路。随着反射次数增加,等效距离变大,区域会迅速收缩,更多次反射不会产生新的有效路径。
CODE:
时间复杂度:O(T×R×600)O(T × R × 600)O(T×R×600)(最坏)(当然实际运行中,由于区域不断收缩,R保持在较小水平,远优于理论最坏情况)
空间复杂度:O(R)O(R)O(R)