Sweep Line & Interval
思路:
不需要检测每一时刻,只需要检测起点或者终点的位置!(交点变化的位置只有起点或者终点)
将数据拆成二元组 [起点/终点标识,时刻]
按照时刻排序
依次扫描
...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: https://www.topcoder.com/community/competitive-programming/tutorials/line-sweep-algorithms/
Template for Point
class Point{
int time;
int flag; // 1=start, 0=end
Point(int time, boolean flag){
this.time = time;
this.flag = flag;
}
public static Comparator<Point> pointComparator = new Comparator<Point>() {
public int compare(Point p1, Point p2){
// 如果时间一致,如果两个都是start或都是end,那么它两相等。如果p1是start而p2是end,那么p1 > p2
if (p1.time == p2.time) return p1.flag - p2.flag;
else return p1.time - p2.time;
}
}
Reference
https://www.topcoder.com/community/competitive-programming/tutorials/line-sweep-algorithms/ 👍
https://courses.csail.mit.edu/6.006/spring11/lectures/lec24.pdf
https://blog.csdn.net/luoshengkim/article/details/72568519
https://en.wikipedia.org/wiki/Sweep_line_algorithm
https://www.hackerearth.com/practice/math/geometry/line-sweep-technique/tutorial/
Last updated
Was this helpful?