시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 84 34 28 46.667%

문제

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

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

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 섬의 꼭짓점의 개수 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+XHJcblxyXG48cD5cdWMxMmNcdWM3NTggXHVjOWMwXHViM2M0XHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YmMxNFx1YjJlNFx1YzY0MCBcdWFjMDBcdWM3YTUgXHViYTQwXHViOWFjIFx1YjVhOFx1YzViNFx1YzgzOFx1Yzc4OFx1YjI5NCBcdWFjZjNcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YzEyY1x1Yzc0MCBcdWJjZmNcdWI4NWQgXHViMmU0XHVhYzAxXHVkNjE1XHVjNzc0XHViYTcwLCBcdWIyZThcdWMyMWMgXHViMmU0XHVhYzAxXHVkNjE1XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzEyY1x1Yzc1OCBcdWFmMmRcdWM5ZDNcdWM4MTBcdWM3NTggXHVhYzFjXHVjMjE4IG4oMyAmbGU7IG4gJmxlOyAxMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIE5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWYyZFx1YzlkM1x1YzgxMFx1Yzc1OCB4XHVjODhjXHVkNDVjXHVjNjQwIHlcdWM4OGNcdWQ0NWNcdWFjMDAgXHViYzE4XHVjMmRjXHVhY2M0XHViYzI5XHVkNWE1XHVjMjFjXHVjMTFjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVhYzAxXHVkNjE1XHVjNzQwIFx1YzEyMFx1YmQ4NCAoeGksIHlpKS0oeGkrMSwgeWkrMSkgKDEgJmxlOyBpICZsZTsgbi0xKVx1YWNmYyAoeG4sIHluKS0oeDEsIHkxKVx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWJhYThcdWI0ZTAgXHVjODhjXHVkNDVjIFx1YWMxMlx1Yzc0MCAwXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWFjZTAsIDEwMDAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0IDBcdWM3NzQgXHVkNTU4XHViMDk4IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1YzEyY1x1YzVkMFx1YzExYyBcdWFjMDBcdWM3YTUgXHViYTQwXHViOWFjIFx1YjVhOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyOTQgXHVhY2YzXHVjNzc0IFx1YzViY1x1YjljY1x1ZDA3YyBcdWI1YThcdWM1YjRcdWM4MzggXHVjNzg4XHViMjk0XHVjOWMwIFx1YWM3MFx1YjlhY1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YzgxNVx1YjJmNVx1YWNmY1x1Yzc1OCBcdWM2MjRcdWNjMjhcdWIyOTQgMC4wMDAwMSgxMDxzdXA+LTU8XC9zdXA+KVx1YWU0Y1x1YzljMCBcdWQ1YzhcdWM2YTlcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMzkwMyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik1vc3QgRGlzdGFudCBQb2ludCBmcm9tIHRoZSBTZWEiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBtYWluIGxhbmQgb2YgSmFwYW4gY2FsbGVkIEhvbnNodSBpcyBhbiBpc2xhbmQgc3Vycm91bmRlZCBieSB0aGUgc2VhLiBJbiBzdWNoIGFuIGlzbGFuZCwgaXQgaXMgbmF0dXJhbCB0byBhc2sgYSBxdWVzdGlvbjogJmxkcXVvO1doZXJlIGlzIHRoZSBtb3N0IGRpc3RhbnQgcG9pbnQgZnJvbSB0aGUgc2VhPyZyZHF1bzsgVGhlIGFuc3dlciB0byB0aGlzIHF1ZXN0aW9uIGZvciBIb25zaHUgd2FzIGZvdW5kIGluIDE5OTYuIFRoZSBtb3N0IGRpc3RhbnQgcG9pbnQgaXMgbG9jYXRlZCBpbiBmb3JtZXIgVXN1ZGEgVG93biwgTmFnYW5vIFByZWZlY3R1cmUsIHdob3NlIGRpc3RhbmNlIGZyb20gdGhlIHNlYSBpcyAxMTQuODZrbS48XC9wPlxyXG5cclxuPHA+SW4gdGhpcyBwcm9ibGVtLCB5b3UgYXJlIGFza2VkIHRvIHdyaXRlIGEgcHJvZ3JhbSB3aGljaCwgZ2l2ZW4gYSBtYXAgb2YgYW4gaXNsYW5kLCBcdWZiMDFuZHMgdGhlIG1vc3QgZGlzdGFudCBwb2ludCBmcm9tIHRoZSBzZWEgaW4gdGhlIGlzbGFuZCwgYW5kIHJlcG9ydHMgaXRzIGRpc3RhbmNlIGZyb20gdGhlIHNlYS4gSW4gb3JkZXIgdG8gc2ltcGxpZnkgdGhlIHByb2JsZW0sIHdlIG9ubHkgY29uc2lkZXIgbWFwcyByZXByZXNlbnRhYmxlIGJ5IGNvbnZleCBwb2x5Z29ucy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb25zaXN0cyBvZiBtdWx0aXBsZSBkYXRhc2V0cy4gRWFjaCBkYXRhc2V0IHJlcHJlc2VudHMgYSBtYXAgb2YgYW4gaXNsYW5kLCB3aGljaCBpcyBhIGNvbnZleCBwb2x5Z29uLiBUaGUgZm9ybWF0IG9mIGEgZGF0YXNldCBpcyBhcyBmb2xsb3dzLjxcL3A+XHJcblxyXG48cHJlPlxyXG5uXHJcbng8c3ViPjE8XC9zdWI+IHk8c3ViPjE8XC9zdWI+XHJcbi4uLlxyXG54PHN1Yj5uPFwvc3ViPiB5PHN1Yj5uPFwvc3ViPjxcL3ByZT5cclxuXHJcbjxwPkV2ZXJ5IGlucHV0IGl0ZW0gaW4gYSBkYXRhc2V0IGlzIGEgbm9uLW5lZ2F0aXZlIGludGVnZXIuIFR3byBpbnB1dCBpdGVtcyBpbiBhIGxpbmUgYXJlIHNlcGFyYXRlZCBieSBhIHNwYWNlLjxcL3A+XHJcblxyXG48cD5uIGluIHRoZSBmaXJzdCBsaW5lIGlzIHRoZSBudW1iZXIgb2YgdmVydGljZXMgb2YgdGhlIHBvbHlnb24sIHNhdGlzZnlpbmcgMyAmbGU7IG4gJmxlOyAxMDAuIFN1YnNlcXVlbnQgbiBsaW5lcyBhcmUgdGhlIHgtIGFuZCB5LWNvb3JkaW5hdGVzIG9mIHRoZSBuIHZlcnRpY2VzLiBMaW5lIHNlZ21lbnRzICh4aSwgeWkpJm5kYXNoOyh4aSsxLCB5aSsxKSAoMSAmbGU7IGkgJmxlOyBuICZtaW51czsgMSkgYW5kIHRoZSBsaW5lIHNlZ21lbnQgKHhuLCB5bikmbmRhc2g7KHgxLCB5MSkgZm9ybSB0aGUgYm9yZGVyIG9mIHRoZSBwb2x5Z29uIGluIGNvdW50ZXJjbG9ja3dpc2Ugb3JkZXIuIFRoYXQgaXMsIHRoZXNlIGxpbmUgc2VnbWVudHMgc2VlIHRoZSBpbnNpZGUgb2YgdGhlIHBvbHlnb24gaW4gdGhlIGxlZnQgb2YgdGhlaXIgZGlyZWN0aW9ucy4gQWxsIGNvb3JkaW5hdGUgdmFsdWVzIGFyZSBiZXR3ZWVuIDAgYW5kIDEwMDAwLCBpbmNsdXNpdmUuPFwvcD5cclxuXHJcbjxwPllvdSBjYW4gYXNzdW1lIHRoYXQgdGhlIHBvbHlnb24gaXMgc2ltcGxlLCB0aGF0IGlzLCBpdHMgYm9yZGVyIG5ldmVyIGNyb3NzZXMgb3IgdG91Y2hlcyBpdHNlbGYuIEFzIHN0YXRlZCBhYm92ZSwgdGhlIGdpdmVuIHBvbHlnb24gaXMgYWx3YXlzIGEgY29udmV4IG9uZS48XC9wPlxyXG5cclxuPHA+VGhlIGxhc3QgZGF0YXNldCBpcyBmb2xsb3dlZCBieSBhIGxpbmUgY29udGFpbmluZyBhIHNpbmdsZSB6ZXJvPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggZGF0YXNldCBpbiB0aGUgaW5wdXQsIG9uZSBsaW5lIGNvbnRhaW5pbmcgdGhlIGRpc3RhbmNlIG9mIHRoZSBtb3N0IGRpc3RhbnQgcG9pbnQgZnJvbSB0aGUgc2VhIHNob3VsZCBiZSBvdXRwdXQuIEFuIG91dHB1dCBsaW5lIHNob3VsZCBub3QgY29udGFpbiBleHRyYSBjaGFyYWN0ZXJzIHN1Y2ggYXMgc3BhY2VzLjxcL3A+XHJcblxyXG48cD5UaGUgYW5zd2VyIHNob3VsZCBub3QgaGF2ZSBhbiBlcnJvciBncmVhdGVyIHRoYW4gMC4wMDAwMSAoMTA8c3VwPiZtaW51czs1PFwvc3VwPikuIFlvdSBtYXkgb3V0cHV0IGFueSBudW1iZXIgb2YgZGlnaXRzIGFmdGVyIHRoZSBkZWNpbWFsIHBvaW50LCBwcm92aWRlZCB0aGF0IHRoZSBhYm92ZSBhY2N1cmFjeSBjb25kaXRpb24gaXMgc2F0aXNcdWZiMDFlZC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

ICPC > Regionals > Asia Pacific > Japan > Asia Regional Contest 2007 in Tokyo I번