비스킷 브레이킹

단순 다각형이 주어졌을 때, 어떤 방향으로든 담을 수 있는 원형 컵의 최소 지름, 즉 다각형의 최소 너비를 구한다.

보통7기하투 포인터정렬아직 제출이 없습니다시간 제한1초메모리 제한512 MB

문제

월터의 회사는 휴게실에 매주 들여놓던 비스킷을 다른 상표로 바꿨다. 새 비스킷에는 이 문제에서 중요한 성질이 두 가지 있다.

  • 비스킷은 완전히 납작해서 평면 도형이다.
  • 비스킷의 테두리는 단순 다각형이다.

그런데 휴게실에 있는 머그컵은 하나같이 입구가 좁다. 세 축을 기준으로 비스킷을 아무리 돌려 봐도 어느 컵에도 넣을 수 없어서, 월터는 머그컵을 새로 주문하기로 했다.

새 머그컵의 입구가 얼마나 넓어야 하는지 구하자. 비스킷 하나의 테두리가 주어지면, 적어도 한 가지 방향으로는 비스킷이 안에 완전히 들어가는 가장 작은 머그컵 지름을 구하면 된다.

입력

  • 첫째 줄에 비스킷의 꼭짓점 개수 NN이 주어진다. (3N1003 \le N \le 100)
  • 다음 NN개 줄 중 ii번째 줄에는 ii번째 꼭짓점의 좌표 XiX_iYiY_i가 공백으로 구분되어 주어진다. (105Xi,Yi105-10^5 \le X_i, Y_i \le 10^5)

꼭짓점은 항상 반시계 방향으로 주어진다. 테두리는 스스로 교차하지 않으며, 비스킷의 넓이는 0보다 크다.

출력

적어도 한 가지 방향으로 비스킷이 완전히 들어가는 가장 작은 머그컵 지름을 출력한다. 소수점 아래 여섯 자리까지 정확히 출력한다. 모든 테스트 케이스의 정답은 반올림 경계에서 10910^{-9}보다 멀리 떨어져 있으므로, 소수점 아래 일곱째 자리에서 반올림하면 된다.