레이팅 미적용농부 존(Farmer John)은 식물을 잘 기르지 못해 애를 먹고 있어서, 물을 제대로 주기 위해 당신의 도움이 필요하다. 2차원 평면에서 N개 (1 <= N <= 100,000)의 빗방울의 위치가 주어진다. 여기서 y는 빗방울의 수직 높이를, x는 1차원 수직선 위에서의 위치를 나타낸다.
각 빗방울은 초당 1단위의 속도로 아래쪽(x축 방향)으로 떨어진다. 당신은 너비 W인 농부 존의 화분을 x축 위 어딘가에 놓아서, 화분에 처음 떨어지는 빗방울과 마지막으로 떨어지는 빗방울 사이의 시간 차가 어떤 값 D 이상이 되게 하고 싶다 (그래야 화분의 꽃들이 물을 충분히 받는다). 화분의 가장자리에 딱 맞게 떨어지는 빗방울도 화분에 떨어진 것으로 센다.
D의 값과 N개의 빗방울의 위치가 주어질 때, 가능한 W의 최솟값을 계산하시오.
첫째 줄: 공백으로 구분된 두 정수 N과 D. (1 <= D <= 1,000,000)
둘째 줄부터 1+N번째 줄까지: i+1번째 줄에 빗방울 i의 (x,y) 좌표가 공백으로 구분되어 주어지며, 각 값은 0...1,000,000 범위이다.
화분의 가능한 최소 너비를 나타내는 정수 하나. D 단위 시간 이상 비를 받을 만큼 넓은 화분을 만들 수 없으면 -1을 출력한다.
fpot.in · 출력을 쓸 파일 fpot.out4 5
6 3
2 4
4 10
12 152Input details: There are 4 raindrops, at (6,3), (2,4), (4,10), and (12,15). Rain must fall on the flowerpot for at least 5 units of time.
Output details: A flowerpot of width 2 is necessary and sufficient, since if we place it from x=4..6, then it captures raindrops #1 and #3, for a total rain duration of 10-3 = 7.