비스킷 브레이킹
시간 제한1초메모리 제한512 MB
단순 다각형이 주어졌을 때, 어떤 방향으로든 담을 수 있는 원형 컵의 최소 지름, 즉 다각형의 최소 너비를 구한다.
문제
월터의 회사는 휴게실에 매주 들여놓던 비스킷을 다른 상표로 바꿨다. 새 비스킷에는 이 문제에서 중요한 성질이 두 가지 있다.
- 비스킷은 완전히 납작해서 평면 도형이다.
- 비스킷의 테두리는 단순 다각형이다.
그런데 휴게실에 있는 머그컵은 하나같이 입구가 좁다. 세 축을 기준으로 비스킷을 아무리 돌려 봐도 어느 컵에도 넣을 수 없어서, 월터는 머그컵을 새로 주문하기로 했다.
새 머그컵의 입구가 얼마나 넓어야 하는지 구하자. 비스킷 하나의 테두리가 주어지면, 적어도 한 가지 방향으로는 비스킷이 안에 완전히 들어가는 가장 작은 머그컵 지름을 구하면 된다.
입력
- 첫째 줄에 비스킷의 꼭짓점 개수 이 주어진다. ()
- 다음 개 줄 중 번째 줄에는 번째 꼭짓점의 좌표 와 가 공백으로 구분되어 주어진다. ()
꼭짓점은 항상 반시계 방향으로 주어진다. 테두리는 스스로 교차하지 않으며, 비스킷의 넓이는 0보다 크다.
출력
적어도 한 가지 방향으로 비스킷이 완전히 들어가는 가장 작은 머그컵 지름을 출력한다. 소수점 아래 여섯 자리까지 정확히 출력한다. 모든 테스트 케이스의 정답은 반올림 경계에서 보다 멀리 떨어져 있으므로, 소수점 아래 일곱째 자리에서 반올림하면 된다.