시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
4 초 | 128 MB | 441 | 81 | 52 | 13.165% |
We will consider a convex polygon with N vertices. We wish to find the maximum radius R such that two circles of radius R can be placed entirely inside the polygon without overlapping.
The first line of input contains the number N. Each of the next N lines contains a pair of integers xi, yi – representing the coordinates of the ith point, separated by space.
You should output a single number R – the desired radius. Output R with a precision of 3 decimals. You will pass a test if the output differs from the true answer by at most 0.001.
4 0 0 1 0 1 1 0 1
0.293
4 0 0 3 0 3 1 0 1
0.500
6 0 0 8 0 8 6 4 8 2 8 0 4
2.189
The maximum radius is obtained when the centers of the two circles are placed on one of the square's diagonals. The radius can be calculated exactly and it is:
\(\dfrac{\sqrt{2}}{2 \times (1 + \sqrt{2})} \approx 0.293\)