착륙장
시간 제한1초메모리 제한128 MB
정수 좌표를 가진 점이 최대 100000개 주어질 때, 경계가 세 점 이상을 지나고 내부에 어떤 점도 포함하지 않는 가장 큰 원을 찾아 R^2을 기약분수로 출력한다.
문제
하늘을 계속 지켜보세요! 외계 우주선이 곧 지구에 착륙해 그들의 앞선 프로그래밍 비법을 전해 줄 예정입니다.
이를 준비하기 위해, 여러분은 들판에 원형 착륙장을 마련해야 합니다. 환경 보호를 위해 들판에 이미 자라고 있는 나무는 한 그루도 베어 낼 수 없습니다. 각 나무는 반지름이 이며, 정수 좌표 위에서만 자랍니다.
보안을 위해 착륙장은 적어도 세 그루의 나무와 맞닿아야 합니다. 맞닿는 나무는 착륙장의 경계(원) 위에 정확히 놓이며, 그 위에 감시 카메라가 설치됩니다. 어떤 나무도 착륙장 내부에 들어와서는 안 됩니다(경계 위에 놓인 나무는 맞닿은 것으로 보며 내부에 있는 것으로 치지 않습니다).
우주선은 완벽한 원 모양이므로 착륙장도 원입니다. 경계가 적어도 세 그루의 나무를 지나면서 내부에는 어떤 나무도 포함하지 않는, 들판에 놓을 수 있는 가장 큰 원형 착륙장의 크기를 구하세요.
입력
첫째 줄에 나무의 수 이 주어집니다 ().
다음 개의 줄에는 각각 한 그루의 나무 좌표를 나타내는 두 정수 와 가 공백으로 구분되어 주어집니다 (). 같은 좌표에 있는 나무는 없습니다.
출력
가장 큰 유효한 착륙장의 반지름을 라고 합시다. 나무의 좌표가 모두 정수이므로 자체는 보통 무리수이지만 은 항상 유리수입니다.
을 기약분수 p/q 형태로 출력하세요. 두 정수를 슬래시(/)로 구분하며, 이고 인 기약분수여야 합니다. 예를 들어 반지름이 인 착륙장은 25/4로 출력합니다.
유효한 착륙장이 적어도 하나 존재하며 임이 보장됩니다.