개구리 징검다리
시간 제한1초메모리 제한256 MB
두 강둑 사이에 돌을 하나 더 놓아 개구리 이동 경로에서 가장 긴 도약 거리를 가장 짧게 만듭니다.
문제
피오나는 개구리가 강을 건너는 게임 Froggy Ford를 만들고 있다. 강은 직선인 두 기슭 과 사이를 흐르고, 물속에는 두 기슭 사이에 돌 개가 놓여 있다.
개구리는 왼쪽 기슭의 아무 점에서나 출발해 돌을 차례로 밟고 오른쪽 기슭의 아무 점에나 도착한다. 기슭에서는 어느 점에서든 뛰고 어느 점에든 내려앉으므로, 점 에 있는 돌과 왼쪽 기슭 사이의 도약 길이는 , 오른쪽 기슭 사이의 도약 길이는 이다. 한 기슭에서 맞은편 기슭으로 곧장 뛰는 도약의 길이는 이고, 돌과 돌 사이의 도약 길이는 두 점의 유클리드 거리이다. 경로는 돌을 원하는 만큼 원하는 순서로 밟고, 경로의 비용은 그 경로에서 가장 긴 도약 하나의 길이이다.
개구리는 힘이 약해서 플레이어는 가장 긴 도약이 가장 짧아지는 경로를 고른다. 피오나는 개구리가 출발하기 전에 플레이어가 돌 하나를 강에 더 놓게 하려고 한다. 새 돌은 , 을 만족하는 실수 좌표 어디에나 놓을 수 있고, 경로가 이 돌을 밟지 않아도 된다.
새 돌을 놓는 모든 방법과 모든 경로 가운데, 가장 긴 도약 길이의 최솟값을 구하여라.
| 최적 경로 | 돌을 하나 더 놓았을 때의 최적 경로 |
|---|---|
 |  |
입력
첫째 줄에 강의 너비 와 돌의 개수 이 주어진다 (, ).
다음 개 줄에 돌 하나의 좌표 , 가 주어진다 (, ). 같은 점에 놓인 돌은 없다.
출력
가장 긴 도약 길이의 최솟값을 소수점 아래 셋째 자리까지 정확히 출력한다. 답이 반올림 경계에 정확히 걸리는 경우는 없다.