시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB41242261.111%

문제

You are given $n$ points on the plane. You have to choose such a straight line, that there will be points on both sides of the line and the minimum distance from one of the points to the line should be the maximum possible. Find this distance.

입력

The first line contains a single integer $n$ --- the number of the points ($2 \le n \le 2\,000$).

Each of the following $n$ lines contains two integers $x_i$ and $y_i$ --- coordinates of $i$-th point ($|x_i|, |y_i| \le 10^9$).

It's guaranteed that no two points coincide.

출력

Print single real number --- an answer. Your answer will be considered correct if its absolute or relative error doesn't exceed $10^{-9}$.

서브태스크

번호배점제한
111

$n \le 10$

219

Points form strictly convex non-degenerate polygon, given in the counter clockwise order, $3 \le n$

323

$n \le 100$

431

$n \le 1\,000$

516

No additional constraints

예제 입력 1

4
0 0
0 1
1 0
1 1

예제 출력 1

0.50000000000

예제 입력 2

2
-12 34
56 -78

예제 출력 2

65.51335741664

예제 입력 3

8
0 0
2 0
5 1
5 3
4 5
3 4
1 4
0 2

예제 출력 3

1.10000000000

힌트

A picture for the third example:

채점 및 기타 정보

  • 예제는 채점하지 않는다.