# Sweep Line & Interval

### **思路：**

不需要检测每一时刻，只需要检测起点或者终点的位置！（交点变化的位置只有起点或者终点）

1. 将数据拆成二元组 \[起点/终点标识，时刻]
2. 按照时刻排序
3. 依次扫描

> ...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**

```java
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://jiayi797.github.io/2018/01/29/%E7%AE%97%E6%B3%95-%E6%89%AB%E6%8F%8F%E7%BA%BF/)

<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/>