시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 8 4 3 42.857%

문제

상근이는 로봇 청소기를 만들고 있다. 로봇 청소기는 청소를 하기 전에 공간을 인식해야 한다.

상근이는 로봇에 들어갈 공간 인식 알고리즘을 작성하고 있다.

방은 볼록 다각형으로 나타낼 수 있다. 또, 로봇은 센서를 이용해서 벽을 인식할 수 있다. 로봇은 자신이 부딪친 벽만 인식할 수 있다. 따라서, 벽을 모두 인식하려면 로봇은 방에 있는 모든 벽에 부딪쳐야 한다.

벽 N개로 이루어진 방(볼록 다각형)과 로봇의 시작 위치 P가 주어진다. 이 때, 모든 벽에 부딪친 다음, 다시 P로 돌아오는 가장 짧은 경로를 구하는 프로그램을 작성하시오. 꼭지점에 로봇이 부딪친 경우에는 두 벽에 부딪친 것이다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에 다각형의 꼭지점 개수 N (3 ≤ N ≤ 100)과 로봇의 시작 위치 Px와 Py가 주어진다. (-10,000 ≤ Px, Py ≤ 10,000) 다음 N개 줄에는 벽의 꼭지점 x, y (-10,000 ≤ x, y ≤ 10,000)가 주어진다. 꼭지점의 순서는 반시계방향 이고, 모든 내부각은 180도보다 작다. 다각형은 교차하지 않으며, 로봇의 시작 위치는 다각형 내부에 있다. (다각형 변 위에 있는 경우는 없다)

출력

각 테스트 케이스 마다, 케이스 번호와 최단 경로의 길이를 소수점 둘째자리까지 출력한다.

예제 입력 1

4 0 0
-1 -1
1 -1
1 1
-1 1
3 10 1
0 0
30 0
0 20

예제 출력 1

Case 1: 5.66
Case 2: 36.73
W3sicHJvYmxlbV9pZCI6IjQyMTAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI4NWNcdWJkMDcgXHVjY2FkXHVjMThjXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViODVjXHViZDA3IFx1Y2NhZFx1YzE4Y1x1YWUzMFx1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWI4NWNcdWJkMDcgXHVjY2FkXHVjMThjXHVhZTMwXHViMjk0IFx1Y2NhZFx1YzE4Y1x1Yjk3YyBcdWQ1NThcdWFlMzAgXHVjODA0XHVjNWQwIFx1YWNmNVx1YWMwNFx1Yzc0NCBcdWM3NzhcdWMyZGRcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViODVjXHViZDA3XHVjNWQwIFx1YjRlNFx1YzViNFx1YWMwOCBcdWFjZjVcdWFjMDQgXHVjNzc4XHVjMmRkIFx1YzU0Y1x1YWNlMFx1YjlhY1x1Yzk5OFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJjMjlcdWM3NDAgXHViY2ZjXHViODVkIFx1YjJlNFx1YWMwMVx1ZDYxNVx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViNjEwLCBcdWI4NWNcdWJkMDdcdWM3NDAgXHVjMTNjXHVjMTFjXHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWJjYmRcdWM3NDQgXHVjNzc4XHVjMmRkXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Yjg1Y1x1YmQwN1x1Yzc0MCBcdWM3OTBcdWMyZTBcdWM3NzQgXHViZDgwXHViNTJhXHVjZTVjIFx1YmNiZFx1YjljYyBcdWM3NzhcdWMyZGRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWJjYmRcdWM3NDQgXHViYWE4XHViNDUwIFx1Yzc3OFx1YzJkZFx1ZDU1OFx1YjgyNFx1YmE3NCBcdWI4NWNcdWJkMDdcdWM3NDAgXHViYzI5XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWJhYThcdWI0ZTAgXHViY2JkXHVjNWQwIFx1YmQ4MFx1YjUyYVx1Y2NkMFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmNiZCBOXHVhYzFjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWJjMjkoXHViY2ZjXHViODVkIFx1YjJlNFx1YWMwMVx1ZDYxNSlcdWFjZmMgXHViODVjXHViZDA3XHVjNzU4IFx1YzJkY1x1Yzc5MSBcdWM3MDRcdWNlNTggUFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIFx1YmFhOFx1YjRlMCBcdWJjYmRcdWM1ZDAgXHViZDgwXHViNTJhXHVjZTVjIFx1YjJlNFx1Yzc0YywgXHViMmU0XHVjMmRjIFBcdWI4NWMgXHViM2NjXHVjNTQ0XHVjNjI0XHViMjk0IFx1YWMwMFx1YzdhNSBcdWM5ZTdcdWM3NDAgXHVhY2JkXHViODVjXHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWFmMmRcdWM5YzBcdWM4MTBcdWM1ZDAgXHViODVjXHViZDA3XHVjNzc0IFx1YmQ4MFx1YjUyYVx1Y2U1YyBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHViNDUwIFx1YmNiZFx1YzVkMCBcdWJkODBcdWI1MmFcdWNlNWMgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwJm5ic3A7XHViMmU0XHVhYzAxXHVkNjE1XHVjNzU4IFx1YWYyZFx1YzljMFx1YzgxMCBcdWFjMWNcdWMyMTggTiAoMyAmbGU7IE4gJmxlOyAxMDApXHVhY2ZjIFx1Yjg1Y1x1YmQwN1x1Yzc1OCBcdWMyZGNcdWM3OTEgXHVjNzA0XHVjZTU4IFB4XHVjNjQwIFB5XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKC0xMCwwMDAgJmxlOyBQeCwgUHkgJmxlOyAxMCwwMDApIFx1YjJlNFx1Yzc0YyBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJjYmRcdWM3NTggXHVhZjJkXHVjOWMwXHVjODEwIHgsIHkgKC0xMCwwMDAgJmxlOyB4LCB5ICZsZTsgMTAsMDAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWYyZFx1YzljMFx1YzgxMFx1Yzc1OCBcdWMyMWNcdWMxMWNcdWIyOTQgXHViYzE4XHVjMmRjXHVhY2M0XHViYzI5XHVkNWE1IFx1Yzc3NFx1YWNlMCwgXHViYWE4XHViNGUwIFx1YjBiNFx1YmQ4MFx1YWMwMVx1Yzc0MCAxODBcdWIzYzRcdWJjZjRcdWIyZTQgXHVjNzkxXHViMmU0LiBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NDAgXHVhZDUwXHVjYzI4XHVkNTU4XHVjOWMwIFx1YzU0YVx1YzczY1x1YmE3MCwgXHViODVjXHViZDA3XHVjNzU4IFx1YzJkY1x1Yzc5MSBcdWM3MDRcdWNlNThcdWIyOTQgXHViMmU0XHVhYzAxXHVkNjE1IFx1YjBiNFx1YmQ4MFx1YzVkMCBcdWM3ODhcdWIyZTQuIChcdWIyZTRcdWFjMDFcdWQ2MTUgXHViY2MwIFx1YzcwNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YjJlNCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNCBcdWI5YzhcdWIyZTQsIFx1Y2YwMFx1Yzc3NFx1YzJhNCBcdWJjODhcdWQ2MzhcdWM2NDAgXHVjZDVjXHViMmU4IFx1YWNiZFx1Yjg1Y1x1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVjMThjXHVjMjE4XHVjODEwIFx1YjQ1OFx1YzlmOFx1Yzc5MFx1YjlhY1x1YWU0Y1x1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNDIxMCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlJvb20gU2VydmljZSIsImRlc2NyaXB0aW9uIjoiPHA+WW91IGFyZSB3b3JraW5nIGZvciBhIGNvbXBhbnkgZGVzaWduaW5nIGN1dGUsIGZ1bm55IHJvYm90IHZhY3V1bSBjbGVhbmVycy4gQXQgYSBoaWdoIGxldmVsLCB0aGUgcm9ib3RzJnJzcXVvOyBiZWhhdmlvciBpcyBkaXZpZGVkIGludG8gdGhyZWUgbW9kZXM6PFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+RXhwbG9yYXRpb248XC9saT5cclxuXHQ8bGk+VmFjdXVtaW5nPFwvbGk+XHJcblx0PGxpPlJhbXBhbnQgS2lsbGluZzxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPlVuZm9ydHVuYXRlbHksIHdoaWxlIGNvbnN1bWVyIHRlc3Rpbmcgc2hvd3MgdGhhdCB0aGUgbGFzdCB0d28gbW9kZXMgYXJlIHdvcmtpbmcgcGVyZmVjdGx5LCB0aGUgZXhwbG9yYXRpb24gbW9kZSBzdGlsbCBoYXMgYnVncy4gWW91JnJzcXVvO3ZlIGJlZW4gcHV0IGluIGNoYXJnZSBvZiBkZWJ1Z2dpbmcuPFwvcD5cclxuXHJcbjxwPkF0IHRoZSBiZWdpbm5pbmcgb2YgdGhlIGV4cGxvcmF0aW9uIG1vZGUsIHRoZSByb2JvdCBpcyBwbGFjZWQgaW50byBhIGNvbnZleCBwb2x5Z29uYWwgcm9vbS4gSXQgaGFzIHNlbnNvcnMgdGhhdCBzaG91bGQgdGVsbCBpdCB3aGVyZSBhbGwgdGhlIHdhbGxzIGFyZS4gWW91ciBqb2IgaXMgdG8gd3JpdGUgYSBwcm9ncmFtIHRoYXQgdmVyaVx1ZmIwMWVzIHRoYXQgdGhlc2UgcmVhZGluZ3MgYXJlIGNvcnJlY3QuIFRvIGRvIHRoaXMsIHRoZSByb2JvdCBuZWVkcyB0byBwaHlzaWNhbGx5IHRvdWNoIGV2ZXJ5IHdhbGwgaW4gdGhlIHJvb20uPFwvcD5cclxuXHJcbjxwPllvdXIgcHJvYmxlbSBpcyB0aGlzOiBnaXZlbiB0aGUgc2hhcGUgb2YgYSBjb252ZXggcG9seWdvbmFsIHJvb20gd2l0aCBOIHdhbGxzIGFuZCBhIHN0YXJ0aW5nIHBvaW50IFAgaW5zaWRlIGl0LCBkZXRlcm1pbmUgdGhlIHNob3J0ZXN0IHJvdXRlIHRoYXQgdG91Y2hlcyBlYWNoIHdhbGwgYW5kIHRoZW4gcmV0dXJucyB0byBQLiBUb3VjaGluZyBhIGNvcm5lciBjb3VudHMgYXMgdG91Y2hpbmcgYm90aCBpbmNpZGVudCB3YWxscy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkVhY2ggdGVzdCBjYXNlIHN0YXJ0cyB3aXRoIGEgbGluZSBjb250YWluaW5nIHRoZSBudW1iZXIgb2YgdmVydGljZXMgTiBvZiB0aGUgcG9seWdvbiAoMyAmbGU7IE4gJmxlOyAxMDApIGFuZCB0aGUgaW50ZWdlciBjb29yZGluYXRlcyBQeCBhbmQgUHkgb2YgdGhlIHJvYm90JnJzcXVvO3Mgc3RhcnRpbmcgcG9pbnQgKC0xMCAwMDAgJmxlOyBQeCwgUHkgJmxlOyAxMCAwMDApLiBUaGlzIGlzIGZvbGxvd2VkIGJ5IE4gbGluZXMsIGVhY2ggY29udGFpbmluZyB0d28gaW50ZWdlcnMgeCwgeSAoLTEwIDAwMCAmbGU7IHgsIHkgJmxlOyAxMCAwMDApIGRlZmluaW5nIGEgdmVydGV4IG9mIHRoZSBwb2x5Z29uLiBWZXJ0aWNlcyBhcmUgZ2l2ZW4gaW4gY291bnRlcmNsb2Nrd2lzZSBvcmRlciwgYWxsIGludGVyaW9yIGFuZ2xlcyBhcmUgbGVzcyB0aGFuIDE4MCBkZWdyZWVzLCB0aGUgcG9seWdvbiBkb2VzIG5vdCBzZWxmLWludGVyc2VjdCwgYW5kIHRoZSByb2JvdCYjMzk7cyBzdGFydGluZyBwb2ludCBpcyBzdHJpY3RseSBpbnNpZGUgdGhlIHBvbHlnb24uPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBkaXNwbGF5IHRoZSBjYXNlIG51bWJlciBhbmQgdGhlIGxlbmd0aCBvZiB0aGUgZGVzaXJlZCByb3V0ZSwgYWNjdXJhdGUgdG8gdHdvIGRlY2ltYWwgcGxhY2VzLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

ACM-ICPC > World Finals > 2012 World Finals H번