Sweep Line & Interval
Last updated
Was this helpful?
Last updated
Was this helpful?
不需要检测每一时刻,只需要检测起点或者终点的位置!(交点变化的位置只有起点或者终点)
将数据拆成二元组 [起点/终点标识,时刻]
按照时刻排序
依次扫描
...the simple but powerful idea of a sweep line: a vertical line that is conceptually “swept” across the plane. In practice, of course, we cannot simulate all points in time and so we consider only some discrete points.
-- TopCoder:
👍