가장 짧은 높이

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

문제

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

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

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

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

입력

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

이후 $N$개의 줄 중 $i$번째 줄에는 $i$번째 점의 좌표를 나타내는 두 정수 $x_i$와 $y_i$가 공백을 사이에 두고 주어진다. $(\lvert x_i\rvert, \lvert y_i \rvert \leq 10^9)$

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

출력

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

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