---
# System prepended metadata

title: Сканирующая прямая

---

# Сканирующая прямая
Основная идея алгоритмы заключается в сортировке событий. Например, **начало отрезка**, **конец отрезка**, **точка**, **человек зашёл в лифт** и.т.д.

# Точка поркытая наибольшим количеством отрезков
Код:
```cpp=

int main() {
    int n;
    cin >> n;
    vector<pair<int, int>> v;
    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        v.push_back({l, 0});// добавляем событие - начало отрезка
        v.push_back({r, 1});// добавляем событие - конец отрезка
    }
    sort(v.begin(), v.end()); // сортируем события
    int ans = 0;
    int ma = -1;
    int now = 0;
    for (auto[x, t] : v) {
        if (t == 0) {
            now++;
        } else {
            now--;
        }
        if (ma < now) {
            ma = now;
            ans = x;
        }
    }
    cout << ans;
}
```
Время работы $n\log{n}$