$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; }
댓글 없음 :
댓글 쓰기