[Algorithm] 철로

http://koitp.org/problem/ICPC_2016DAJI_RAILWAY/read/

시간 제한	메모리 제한	제출 횟수	정답 횟수 (비율)	정답자 수
1.0 초	512 MB	588	75 (13%)	65

문제

집과 사무실을 통근하는 $n$명의 사람들이 있다. 각 사람의 집과 사무실은 수평선 상에 있는 서로 다른 점에 위치하고 있다. 임의의 두 사람 $A,B$에 대하여, $A$의 집 혹은 사무실의 위치가 $B$의 집 혹은 사무실의 위치와 같을 수 있다. 통근을 하는 사람들의 편의를 위하여 일직선 상의 어떤 두 점을 잇는 철로를 건설하여, 기차를 운행하려고 한다. 제한된 예산 때문에, 철로의 길이는 $d$로 정해져 있다. 집과 사무실의 위치 모두 철로 선분에 포함되는 사람들의 수가 최대가 되도록, 철로 선분을 정하고자 한다.

양의 정수 $d$와 $n$개의 정수쌍, $(h_i,o_i),1\le i\le n$,이 주어져 있다. 여기서 $h_i$와 $o_i$는 사람 $i$의 집과 사무실의 위치이다. 길이 $d$의 모든 선분$L$에 대하여, 집과 사무실의 위치가 모두 $L$에 포함되는 사람들의 최대 수를 구하는 프로그램을 작성하시오.

위의 그림에 있는 예를 고려해보자. 여기서 $n=8$, $(h_1,o_1)=(5,40)$,$(h_2,o_2)=(35,25)$, $(h_3,o_3)=(10,20)$, $(h_4,o_4)=(10,25)$, $(h_5,o_5)=(30,50)$, $(h_6,o_6)=(50,60)$, $(h_7,o_7)=(30,25)$, $(h_8,o_8)=(80,100)$이고, $d=30$이다. 이 예에서, 위치 $10$과 $40$사이의 빨간색 선분 $L$이, 가장 많은 사람들에 대하여 집과 사무실 위치 모두 포함되는 선분 중 하나이다. 따라서 답은 $4$이다.

입력

첫 번째 줄에 사람 수를 나타내는 양의 정수 $n(1\le n\le 100,000)$이 주어진다. 다음 $n$개의 각 줄에 정수 쌍 $(h_i,o_i)$가 주어진다. 여기서 $h_i$와 $o_i$는 $-100,000,000$이상, $100,000,000$이하의 서로 다른 정수이다. 마지막 줄에, 철로의 길이를 나타내는 정수 $d(1\le d\le 200,000,000)$가 주어진다.

출력

길이 $d$의 임의의 선분에 대하여, 집과 사무실 위치가 모두 그 선분에 포함되는 사람들의 최대 수를 한 줄에 출력한다.

힌트

입력 예제 1

8
5 40
35 25
10 20
10 25
30 50
50 60
30 25
80 100
30

출력 예제 1

4

입력 예제 2

4
20 80
70 30
35 65
40 60
10

출력 예제 2

0

입력 예제 3

5
-5 5
30 40
-5 5
50 40
5 -5
10

출력 예제 3

3