안전 거리
시간 제한1초메모리 제한512 MB
직사각형 방 안에서 N개의 점 장애물을 피해 (0,0)에서 (X,Y)로 이동할 때, 장애물까지의 최소 거리를 최대화하는 경로를 찾는다.
문제
지난 한 해는 힘들었다. 바이러스가 사람들 사이에 퍼졌기 때문이다. 다행히도 Alice는 건강을 지키는 방법 중 하나가 다른 사람들과 안전한 거리를 유지하는 것이라는 사실을 알고 있다.
Alice는 현재 가로 , 세로 인 닫힌 방 안에 있다. 방 안에는 다른 사람 명이 있고, 그들의 좌표 가 주어진다.
Alice와 명의 사람을 평면 위의 점으로 생각한다. Alice의 처음 위치는 이고, 그녀는 출구인 로 이동하려고 한다. 그녀는 방 안에서 어느 방향으로든 자유롭게 움직일 수 있지만, 방의 경계를 벗어날 수는 없다.
에서 로 이동하는 동안 Alice가 다른 사람들로부터 유지할 수 있는 최대 거리를 구하여라.
입력
첫 번째 줄에는 방의 가로 와 세로 를 나타내는 두 정수가 공백으로 구분되어 주어진다. 두 번째 줄에는 방 안에 있는 사람 수 이 주어진다. 그다음 개의 줄에 걸쳐 각 줄에 방 안의 번째 사람의 좌표 , 가 두 실수로 주어진다.
출력
최대 안전 거리 를 실수 하나로 출력한다.
덧셈 또는 곱셈 오차 까지 허용된다. 즉 가 정답일 때, 안에 있거나 안에 있는 수는 모두 정답으로 인정된다.