시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 19 8 7 41.176%

문제

상근이는 추석 연휴에 아름다운 자연 경관을 자랑하는 제주도로 놀러가기로 했다. 제주도 지도를 보면서 여행 계획을 세우던 상근이는 갑자기 바다에서 가장 멀리 떨어져 있는 곳이 어딘지 궁금해졌다.

섬의 지도가 주어졌을 때, 바다와 가장 멀리 떨어져있는 곳을 구하는 프로그램을 작성하시오. 섬은 볼록 다각형이며, 단순 다각형이다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 섬의 꼭짓점의 개수 n(3 ≤ n ≤ 100)이 주어진다. 다음 N개 줄에는 꼭짓점의 x좌표와 y좌표가 반시계방향순서로 주어진다. 다각형은 선분 (xi, yi)-(xi+1, yi+1) (1 ≤ i ≤ n-1)과 (xn, yn)-(x1, y1)으로 이루어져 있다. 모든 좌표 값은 0보다 크거나 같고, 10000보다 작거나 같다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력

각 테스트 케이스에 대해서, 섬에서 가장 멀리 떨어져 있는 곳이 얼만큼 떨어져 있는지 거리를 출력한다. 정답과의 오차는 0.00001(10-5)까지 허용된다.

예제 입력 1

4
0 0
10000 0
10000 10000
0 10000
3
0 0
10000 0
7000 1000
6
0 40
100 20
250 40
250 70
100 90
0 70
3
0 0
10000 10000
5000 5001
0

예제 출력 1

5000.000000
494.233641
34.542948
0.353553
W3sicHJvYmxlbV9pZCI6IjM5MDMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4MWNcdWM4ZmNcdWIzYzQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWNkOTRcdWMxMWQgXHVjNWYwXHVkNzM0XHVjNWQwIFx1YzU0NFx1Yjk4NFx1YjJlNFx1YzZiNCBcdWM3OTBcdWM1ZjAgXHVhY2JkXHVhZDAwXHVjNzQ0IFx1Yzc5MFx1Yjc5MVx1ZDU1OFx1YjI5NCBcdWM4MWNcdWM4ZmNcdWIzYzRcdWI4NWMgXHViMTgwXHViN2VjXHVhYzAwXHVhZTMwXHViODVjIFx1ZDU4OFx1YjJlNC4gXHVjODFjXHVjOGZjXHViM2M0IFx1YzljMFx1YjNjNFx1Yjk3YyBcdWJjZjRcdWJhNzRcdWMxMWMgXHVjNWVjXHVkNTg5IFx1YWNjNFx1ZDY4ZFx1Yzc0NCBcdWMxMzhcdWM2YjBcdWIzNTggXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YWMxMVx1Yzc5MFx1YWUzMCBcdWJjMTRcdWIyZTRcdWM1ZDBcdWMxMWMgXHVhYzAwXHVjN2E1IFx1YmE0MFx1YjlhYyBcdWI1YThcdWM1YjRcdWM4MzggXHVjNzg4XHViMjk0IFx1YWNmM1x1Yzc3NCBcdWM1YjRcdWI1MThcdWM5YzAgXHVhZDgxXHVhZTA4XHVkNTc0XHVjODRjXHViMmU0LjxcL3A+XHJcblxyXG5cclxuXHJcbjxwPlx1YzEyY1x1Yzc1OCBcdWM5YzBcdWIzYzRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHViYzE0XHViMmU0XHVjNjQwIFx1YWMwMFx1YzdhNSBcdWJhNDBcdWI5YWMgXHViNWE4XHVjNWI0XHVjODM4XHVjNzg4XHViMjk0IFx1YWNmM1x1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVjMTJjXHVjNzQwIFx1YmNmY1x1Yjg1ZCBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NzRcdWJhNzAsIFx1YjJlOFx1YzIxYyBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMTJjXHVjNzU4IFx1YWYyZFx1YzlkM1x1YzgxMFx1Yzc1OCBcdWFjMWNcdWMyMTggbigzICZsZTsgbiAmbGU7IDEwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhZjJkXHVjOWQzXHVjODEwXHVjNzU4IHhcdWM4OGNcdWQ0NWNcdWM2NDAgeVx1Yzg4Y1x1ZDQ1Y1x1YWMwMCBcdWJjMThcdWMyZGNcdWFjYzRcdWJjMjlcdWQ1YTVcdWMyMWNcdWMxMWNcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NDAgXHVjMTIwXHViZDg0ICh4aSwgeWkpLSh4aSsxLCB5aSsxKSAoMSAmbGU7IGkgJmxlOyBuLTEpXHVhY2ZjICh4biwgeW4pLSh4MSwgeTEpXHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWM4OGNcdWQ0NWMgXHVhYzEyXHVjNzQwIDBcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YWNlMCwgMTAwMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuXHJcblxyXG48cD5cdWM3ODVcdWI4MjVcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCAwXHVjNzc0IFx1YjQ1MCBcdWFjMWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVjMTJjXHVjNWQwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWJhNDBcdWI5YWMgXHViNWE4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjI5NCBcdWFjZjNcdWM3NzQgXHVjNWJjXHViOWNjXHVkMDdjIFx1YjVhOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVhYzcwXHViOWFjXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjODE1XHViMmY1XHVhY2ZjXHVjNzU4IFx1YzYyNFx1Y2MyOFx1YjI5NCAwLjAwMDAxKDEwPHN1cD4tNTxcL3N1cD4pXHVhZTRjXHVjOWMwIFx1ZDVjOFx1YzZhOVx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzOTAzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTW9zdCBEaXN0YW50IFBvaW50IGZyb20gdGhlIFNlYSIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIG1haW4gbGFuZCBvZiBKYXBhbiBjYWxsZWQgSG9uc2h1IGlzIGFuIGlzbGFuZCBzdXJyb3VuZGVkIGJ5IHRoZSBzZWEuIEluIHN1Y2ggYW4gaXNsYW5kLCBpdCBpcyBuYXR1cmFsIHRvIGFzayBhIHF1ZXN0aW9uOiAmbGRxdW87V2hlcmUgaXMgdGhlIG1vc3QgZGlzdGFudCBwb2ludCBmcm9tIHRoZSBzZWE/JnJkcXVvOyBUaGUgYW5zd2VyIHRvIHRoaXMgcXVlc3Rpb24gZm9yIEhvbnNodSB3YXMgZm91bmQgaW4gMTk5Ni4gVGhlIG1vc3QgZGlzdGFudCBwb2ludCBpcyBsb2NhdGVkIGluIGZvcm1lciBVc3VkYSBUb3duLCBOYWdhbm8gUHJlZmVjdHVyZSwgd2hvc2UgZGlzdGFuY2UgZnJvbSB0aGUgc2VhIGlzIDExNC44NmttLjxcL3A+XHJcblxyXG48cD5JbiB0aGlzIHByb2JsZW0sIHlvdSBhcmUgYXNrZWQgdG8gd3JpdGUgYSBwcm9ncmFtIHdoaWNoLCBnaXZlbiBhIG1hcCBvZiBhbiBpc2xhbmQsIFx1ZmIwMW5kcyB0aGUgbW9zdCBkaXN0YW50IHBvaW50IGZyb20gdGhlIHNlYSBpbiB0aGUgaXNsYW5kLCBhbmQgcmVwb3J0cyBpdHMgZGlzdGFuY2UgZnJvbSB0aGUgc2VhLiBJbiBvcmRlciB0byBzaW1wbGlmeSB0aGUgcHJvYmxlbSwgd2Ugb25seSBjb25zaWRlciBtYXBzIHJlcHJlc2VudGFibGUgYnkgY29udmV4IHBvbHlnb25zLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnNpc3RzIG9mIG11bHRpcGxlIGRhdGFzZXRzLiBFYWNoIGRhdGFzZXQgcmVwcmVzZW50cyBhIG1hcCBvZiBhbiBpc2xhbmQsIHdoaWNoIGlzIGEgY29udmV4IHBvbHlnb24uIFRoZSBmb3JtYXQgb2YgYSBkYXRhc2V0IGlzIGFzIGZvbGxvd3MuPFwvcD5cclxuXHJcbjxwcmU+XHJcbm5cclxueDxzdWI+MTxcL3N1Yj4geTxzdWI+MTxcL3N1Yj5cclxuLi4uXHJcbng8c3ViPm48XC9zdWI+IHk8c3ViPm48XC9zdWI+PFwvcHJlPlxyXG5cclxuPHA+RXZlcnkgaW5wdXQgaXRlbSBpbiBhIGRhdGFzZXQgaXMgYSBub24tbmVnYXRpdmUgaW50ZWdlci4gVHdvIGlucHV0IGl0ZW1zIGluIGEgbGluZSBhcmUgc2VwYXJhdGVkIGJ5IGEgc3BhY2UuPFwvcD5cclxuXHJcbjxwPm4gaW4gdGhlIGZpcnN0IGxpbmUgaXMgdGhlIG51bWJlciBvZiB2ZXJ0aWNlcyBvZiB0aGUgcG9seWdvbiwgc2F0aXNmeWluZyAzICZsZTsgbiAmbGU7IDEwMC4gU3Vic2VxdWVudCBuIGxpbmVzIGFyZSB0aGUgeC0gYW5kIHktY29vcmRpbmF0ZXMgb2YgdGhlIG4gdmVydGljZXMuIExpbmUgc2VnbWVudHMgKHhpLCB5aSkmbmRhc2g7KHhpKzEsIHlpKzEpICgxICZsZTsgaSAmbGU7IG4gJm1pbnVzOyAxKSBhbmQgdGhlIGxpbmUgc2VnbWVudCAoeG4sIHluKSZuZGFzaDsoeDEsIHkxKSBmb3JtIHRoZSBib3JkZXIgb2YgdGhlIHBvbHlnb24gaW4gY291bnRlcmNsb2Nrd2lzZSBvcmRlci4gVGhhdCBpcywgdGhlc2UgbGluZSBzZWdtZW50cyBzZWUgdGhlIGluc2lkZSBvZiB0aGUgcG9seWdvbiBpbiB0aGUgbGVmdCBvZiB0aGVpciBkaXJlY3Rpb25zLiBBbGwgY29vcmRpbmF0ZSB2YWx1ZXMgYXJlIGJldHdlZW4gMCBhbmQgMTAwMDAsIGluY2x1c2l2ZS48XC9wPlxyXG5cclxuPHA+WW91IGNhbiBhc3N1bWUgdGhhdCB0aGUgcG9seWdvbiBpcyBzaW1wbGUsIHRoYXQgaXMsIGl0cyBib3JkZXIgbmV2ZXIgY3Jvc3NlcyBvciB0b3VjaGVzIGl0c2VsZi4gQXMgc3RhdGVkIGFib3ZlLCB0aGUgZ2l2ZW4gcG9seWdvbiBpcyBhbHdheXMgYSBjb252ZXggb25lLjxcL3A+XHJcblxyXG48cD5UaGUgbGFzdCBkYXRhc2V0IGlzIGZvbGxvd2VkIGJ5IGEgbGluZSBjb250YWluaW5nIGEgc2luZ2xlIHplcm88XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBkYXRhc2V0IGluIHRoZSBpbnB1dCwgb25lIGxpbmUgY29udGFpbmluZyB0aGUgZGlzdGFuY2Ugb2YgdGhlIG1vc3QgZGlzdGFudCBwb2ludCBmcm9tIHRoZSBzZWEgc2hvdWxkIGJlIG91dHB1dC4gQW4gb3V0cHV0IGxpbmUgc2hvdWxkIG5vdCBjb250YWluIGV4dHJhIGNoYXJhY3RlcnMgc3VjaCBhcyBzcGFjZXMuPFwvcD5cclxuXHJcbjxwPlRoZSBhbnN3ZXIgc2hvdWxkIG5vdCBoYXZlIGFuIGVycm9yIGdyZWF0ZXIgdGhhbiAwLjAwMDAxICgxMDxzdXA+Jm1pbnVzOzU8XC9zdXA+KS4gWW91IG1heSBvdXRwdXQgYW55IG51bWJlciBvZiBkaWdpdHMgYWZ0ZXIgdGhlIGRlY2ltYWwgcG9pbnQsIHByb3ZpZGVkIHRoYXQgdGhlIGFib3ZlIGFjY3VyYWN5IGNvbmRpdGlvbiBpcyBzYXRpc1x1ZmIwMWVkLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==