가장 짧은 높이

시간 제한4초메모리 제한32 MB

요약
주어진 점들 중 서로 다른 세 점으로 만든 모든 삼각형에서 가장 짧은 높이의 최솟값을 실수로 출력한다.
난이도

어려움10점 중 8점

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

문제

메모리 제한에 유의하여라.

좌표평면 위에 NN개의 점이 있다.

이 점들 중 서로 다른 세 개를 골라서 만들 수 있는 삼각형의 세 개의 높이 중 가장 짧은 것의 최솟값을 구하여라.

세 점이 한 직선 위에 있어 삼각형의 높이가 0이 될 수 있음에 유의하여라.

입력

첫 번째 줄에는 점의 개수를 나타내는 정수 NN이 주어진다. (3≤N≤4,000)(3\leq N\leq 4\\, 000)

이후 NN개의 줄 중 ii번째 줄에는 ii번째 점의 좌표를 나타내는 두 정수 x_ix\_i와 y_iy\_i가 공백을 사이에 두고 주어진다. (∣x_i∣,∣y_i∣≤109)(\lvert x\_i\rvert, \lvert y\_i \rvert \leq 10^9)

동일한 위치의 점은 입력으로 들어오지 않는다.

출력

입력으로 주어진 NN개의 점 중 서로 다른 세 개를 골라 삼각형을 만들었을 때 가능한 높이 중 가장 짧은 것을 출력한다.

출력한 답과 정답과의 상대 또는 절대 오차가 10−610^{-6} 이하여야 한다.

예제3

  1. 예제 1

    입력
    3
    1 1
    2 4
    3 5
    
    예상 출력
    0.4472136
    
  2. 예제 2

    입력
    3
    -2 -2
    0 0
    1 1
    
    예상 출력
    0
    
  3. 예제 3

    입력
    4
    10 7
    2 -3
    -8 5
    0 -9
    
    예상 출력
    1.4839970