문제
택쌤은 동물원에서 팬더를 구경하던 중, 한쪽 구석에서 가면과 검은 가면을 쓰고, 큰 보따리를 지닌 한 무리의 사람들을 발견했다. 택쌤은 이들을 팬더 도둑이라고 의심하고, 팬더를 지켜주고 싶은 마음에 동물원에 연락하여 조치를 취하도록 했다. 이에 동물원은 팬더 감시망을 강화하기로 하였다.
팬더들이 사는 곳은 다각형 모양의 철조망으로 둘러 쌓여 있다. 팬더들을 감시하는 카메라는 다각형의 꼭지점에 위치해 있다. 이 카메라는 최대 r미터 만큼 감시할 수 있다고 한다. 당연히 더 멀리 볼 수 있는 카메라가 더 비싸기 때문에, 동물원은 이 유효 감시 거리인 r을 최소화 시키려고 한다. 동물원은 프로그래머인 택쌤에게 그 최소값을 물어보았다. 물론 프로그램을 작성하는건 여러분이지만 말이다.
입력
첫째 줄에 n(3 <= n <= 2,000)이 주어지며, 이는 다각형의 꼭지점 개수다.
다음 둘째 줄부터 (n+1)번째 줄까지 n개의 줄에는, 정수 x와 y가 주어지며(-104 <= x, y <= 104) 이는 각 꼭지점이다.
꼭지점은 무조건 첫째 좌표부터 반 시계 방향으로 입력된다.
다각형이기 때문에, 꼭지점 이외의 좌표에서 다각형의 변이 교차하는 일은 없다.
출력
카메라의 최소 유효 거리인 r을 출력하라. 절대적인 정답과의 10-6(0.000001)까지의 오차는 정답으로 간주한다.
예제 #1
5
0 0
170 0
140 30
60 300 70
50
예제 #2
5
0 0
170 0
140 30
60 300 100
51.538820320
예제 #3
5
0 0
1 2
1 5
0 20 1
1.581138830
힌트
출처
ACM-ICPC 2018 World Final Problem G: Panda Preserve
로그인해야 코드를 작성할 수 있어요.