求助站外题(疑似李超树?)
  • 板块学术版
  • 楼主never_AK
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/11/4 08:08
  • 上次更新2024/11/4 16:00:51
查看原帖
求助站外题(疑似李超树?)
373757
never_AK楼主2024/11/4 08:08

在平面直角坐标系中

给定N条蓝线段(1N8×1051 \le N \le 8\times10^5

每条线段有一个横坐标 xix_i 和长度 yiy_i,表示该线段覆盖了(x_i,t)这段区域(0tyi0 \le t \le y_i)

对于Q个询问(1Q3×1051 \le Q \le 3\times 10 ^ 5

每个询问有一个起点S的坐标(Sx,SyS_x,S_y)和终点坐标E(Ex,EyE_x,E_y),表示一条S -> E 的红线段,输出是否有之前给定的蓝线段与红线段相交,如果有,输出任意一条蓝线段的编号,否则输出-1

感觉有点像李超树,但好像又不太可做

2024/11/4 08:08
加载中...