경비행기
시간 제한1초메모리 제한128 MB
고정된 출발점과 도착점 사이 최대 1000개의 경유 공항이 주어질 때, 중간 착륙을 k회 이하로 하면서 이동 가능한 최소 연료통 용량(구간별 최대 연료 소모량)을 이분 탐색과 경로 존재 판정으로 구합니다.
문제
경비행기 독수리호는 출발지 S에서 목적지 T까지 가능한 빠르게 이동하려고 한다. 연료통이 크면 중간에 착륙해 급유하는 횟수를 줄일 수 있지만, 무게 때문에 속도와 안정성에 문제가 생길 수 있다. 반대로 연료통이 작으면 비행은 빨라지지만 더 자주 급유해야 한다.
최대 k번 이하로 중간 급유지에 착륙할 수 있을 때, S에서 T까지 이동하는 데 필요한 연료통의 최소 용량을 구하라.
그림과 같은 상황에서 허용되는 중간 착륙 횟수가 k = 2라면, 어떤 경로는 마지막 구간이 매우 길어 큰 연료통이 필요할 수 있다. 목표는 허용된 중간 착륙 횟수 안에서 각 비행 구간의 필요 연료량 중 최댓값을 최소화하는 것이다.
다음 조건을 따른다.
- 모든 비행기는 두 지점 사이를 직선으로만 이동한다. 거리 단위는 km이고 연료 단위는 L이다. 연료 1L로 10km를 비행할 수 있으며, 연료는 정수 L 단위로 주입한다.
- 두 위치 사이의 거리는 평면상의 유클리드 거리이다. 예를 들어
g = (2, 1),h = (37, 43)이면 거리d(g, h)는 \(\sqrt{(2-37)^2 + (1-43)^2}\) = 54.671... 이다. 따라서50 < d(g, h) <= 60이므로 이 구간에는 6L가 필요하다. - 출발지 S의 좌표는 항상
(0, 0), 목적지 T의 좌표는 항상(10000, 10000)이다. - 출발지와 목적지를 제외한 비행장의 수
n은3 <= n <= 1000이다. 각 비행장 좌표(x, y)는0 < x, y < 10000인 정수이다. 최대 허용 중간 급유 횟수k는0 <= k <= 1000이다.
입력
첫째 줄에 비행장의 수 n과 최대 허용 중간 급유 횟수 k가 공백으로 구분되어 주어진다.
다음 n개의 줄에는 각 비행장(급유지)의 정수 좌표 x y가 한 줄에 하나씩 주어진다.
출력
S에서 T까지 중간 급유를 k번 이하로 하며 이동할 수 있도록 하는 연료통의 최소 용량을 정수로 출력한다.