아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

착륙장

시간 제한1초메모리 제한128 MB

요약
정수 좌표를 가진 점이 최대 100000개 주어질 때, 경계가 세 점 이상을 지나고 내부에 어떤 점도 포함하지 않는 가장 큰 원을 찾아 R^2을 기약분수로 출력한다.
난이도

어려움10점 중 9점

유형
기하, 조합론, 수학, 정렬
정답자
아직 제출이 없습니다

문제

하늘을 계속 지켜보세요! 외계 우주선이 곧 지구에 착륙해 그들의 앞선 프로그래밍 비법을 전해 줄 예정입니다.

이를 준비하기 위해, 여러분은 들판에 원형 착륙장을 마련해야 합니다. 환경 보호를 위해 들판에 이미 자라고 있는 나무는 한 그루도 베어 낼 수 없습니다. 각 나무는 반지름이 00이며, 정수 좌표 위에서만 자랍니다.

보안을 위해 착륙장은 적어도 세 그루의 나무와 맞닿아야 합니다. 맞닿는 나무는 착륙장의 경계(원) 위에 정확히 놓이며, 그 위에 감시 카메라가 설치됩니다. 어떤 나무도 착륙장 내부에 들어와서는 안 됩니다(경계 위에 놓인 나무는 맞닿은 것으로 보며 내부에 있는 것으로 치지 않습니다).

우주선은 완벽한 원 모양이므로 착륙장도 원입니다. 경계가 적어도 세 그루의 나무를 지나면서 내부에는 어떤 나무도 포함하지 않는, 들판에 놓을 수 있는 가장 큰 원형 착륙장의 크기를 구하세요.

입력

첫째 줄에 나무의 수 nn이 주어집니다 (3≤n≤1000003 \le n \le 100000).

다음 nn개의 줄에는 각각 한 그루의 나무 좌표를 나타내는 두 정수 xx와 yy가 공백으로 구분되어 주어집니다 (−10000≤x,y≤10000-10000 \le x, y \le 10000). 같은 좌표에 있는 나무는 없습니다.

출력

가장 큰 유효한 착륙장의 반지름을 RR라고 합시다. 나무의 좌표가 모두 정수이므로 RR 자체는 보통 무리수이지만 R2R^2은 항상 유리수입니다.

R2R^2을 기약분수 p/q 형태로 출력하세요. 두 정수를 슬래시(/)로 구분하며, q>0q > 0이고 gcd⁡(p,q)=1\gcd(p, q) = 1인 기약분수여야 합니다. 예를 들어 반지름이 52\tfrac{5}{2}인 착륙장은 25/4로 출력합니다.

유효한 착륙장이 적어도 하나 존재하며 R<109R < 10^9임이 보장됩니다.

예제3

  1. 예제 1

    입력
    4
    1 1
    1 -1
    -1 -1
    -1 1
    
    예상 출력
    2/1
    
  2. 예제 2

    입력
    3
    0 0
    4 0
    0 3
    
    예상 출력
    25/4
    
  3. 예제 3

    입력
    3
    0 0
    2 0
    1 2
    
    예상 출력
    25/16