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

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

또 다른 미니맥스 문제

시간 제한2초메모리 제한512 MB

요약
정수 좌표의 점 n개가 주어질 때, 양쪽에 점이 놓이도록 직선을 골라 점들과 직선 사이의 최소 거리를 최대로 만드는 값을 구합니다.
난이도

어려움10점 중 9점

유형
기하, 이분 탐색, 정렬
정답자
아직 제출이 없습니다

문제

평면 위에 점 nn개가 주어진다. 직선을 하나 골라야 하는데, 직선의 양쪽에 모두 점이 있어야 한다. 점들 중 하나에서 직선까지의 거리의 최솟값이 가능한 한 크도록 직선을 고른다. 이때의 거리를 구하라.

입력

첫 줄에 점의 개수 nn이 주어진다 (2≤n≤2 0002 \le n \le 2\,000). 다음 nn개 줄에는 ii번째 점의 좌표 정수 xix_i와 yiy_i가 주어진다 (∣xi∣,∣yi∣≤109|x_i|, |y_i| \le 10^9). 같은 점이 두 번 주어지지 않는다.

출력

답을 실수 하나로 출력한다. 절대 오차 또는 상대 오차가 10−910^{-9} 이하이면 정답으로 인정한다.

힌트

예제3

  1. 예제 1

    입력
    4
    0 0
    0 1
    1 0
    1 1
    
    예상 출력
    0.50000000000
    
  2. 예제 2

    입력
    2
    -12 34
    56 -78
    
    예상 출력
    65.51335741664
    
  3. 예제 3

    입력
    8
    0 0
    2 0
    5 1
    5 3
    4 5
    3 4
    1 4
    0 2
    
    예상 출력
    1.10000000000