13334번: 철로

https://www.acmicpc.net/problem/13334


$O(n\lg n)$

집과 사무실 사이 구간을 [xi,yi](xi<=yi)로 표현한다. 구간 길이가 d보다 큰 쌍은 모두 제외하자.
좌표축에 수직이며 거리 차가 d인 두 직선을 이용하여 왼쪽에서 오른쪽으로 스위핑해보면
i번째 구간이 철로 구간에 포함되는 시점은 오른쪽 직선이 xi일 때이고
배제되는 시점은 왼쪽 직선이 yi일 때이다.
이를 주목하여 한 직선과 연관되는 점들을 평행이동을 시키면
하나의 직선의 스위핑으로 철로 구간 내 [xi,yi] 구간의 개수를 카운트 할 수 있다.
모든 (yi-d,1), (xi,-1) 쌍을 첫번째 원소를 기준으로 오름차순 정렬한다.
(첫번째 원소가 같으면 두번째 원소를 기준으로 내림차순 정렬한다.)
이제 앞에서부터 두번째 원소를 하나의 변수 s에 누적해가면서 최댓값을 구한다. 이 값이 답이다.

#include<cstdio>
#include<algorithm>
using namespace std;
int x[100000], y[100000], cnt, s, r, n, d;
pair<int, int> p[200000];
int main() {
    scanf("%d", &n);
    for (int i = 0; i<n; i++) scanf("%d%d", x + i, y + i);
    scanf("%d", &d);
    for (int i = 0; i<n; i++) {
        if (x[i]>y[i]) swap(x[i], y[i]);
        if (y[i] - x[i]>d) continue;
        p[cnt++] = { y[i] - d,-1 };
        p[cnt++] = { x[i],1 };
    }
    sort(p, p + cnt);
    for (int i = 0; i<cnt; i++) {
        s -= p[i].second;
        if (r<s) r = s;
    }
    printf("%d", r);
    return 0;
}