문제
열대 섬에 있는 Piconesia는 예쁜 바닷가, 무성한 초목, 코코아와 커피 재배지, 그리고 훌륭한 날씨로 유명한 나라이다. 이 천국과 같은 장소는 ICPC World Final의 개최지(혹은, 적어도 집행 위원회의 휴가 장소로)로 고려되고 있다. 여기에는 단 한 가지의 문제점이 있는데, 섬에 가기 매우 어렵다는 것이다.
현재, 가장 가까운 공항에서 섬으로 가는데는 3일이 걸리고, 낚시배, 기름 수송선, 카약, 잠수함을 이용해야만 갈 수 있다. ICPC World Final을 쉽게 개최할 수 있도록 하면서, 섬의 관광 산업을 시작하기 위해, Piconesia는 첫 번째 공항을 짓기로 결심하였다.
긴 활주로는 큰 비행기를 수용할 수 있기 때문에, Piconesia는 그들의 섬에 지을 수 있는 가장 긴 활주로를 짓기로 결심하였다. 불행하게도, 그들은 활주로를 어디에 위치시켜야 가장 긴 활주로가 되는지 알 수 없었다.
이 문제에서는 Piconesia의 가장자리를 다각형이라고 모델링하였다. 이 다각형이 주어졌을 때, 여러분은 섬에 지을 수 있는 가장 긴 활주로의 길이를 구해야 한다. 활주로는 섬 밖으로 나갈 수 없지만, 섬의 가장자리와 만나는 것은 가능하다. 그림은 첫 번째 예제의 모습을 나타낸다.
입력
첫 번째 줄에 다각형의 꼭지점 개수 n이 주어진다. (3 ≤ n ≤ 200)
다음 n개의 줄에, 다각형의 꼭지점 위치를 나타내는 2개의 정수 x, y가 주어진다. (|x|, |y| ≤ 106)
점들은 시계 반대 방향으로 주어진다. 주어진 다각형은 simple polygon임이 보장된다. 이는 모든 점이 다르며, 인접한 두 변이 꼭지점에서 교차하는 것을 제외하고는 어떤 두 변도 교차하지 않는다는 것을 의미한다. 추가로, 어떤 두 변도 일직선이 아니다.
출력
가장 긴 활주로 길이를 첫 번째 줄에 출력한다. 상대 및 절대 오차는 10-6 이하여야 한다.
예제 #1
7
0 20
40 0
40 20
70 50
50 70
30 50
0 50
76.157731059
예제 #2
3
0 2017
-2017 -2017
2017 0
4510.149110617
로그인해야 코드를 작성할 수 있어요.