시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 128 MB298736.842%

문제

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

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

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

벽 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+XHJcblxyXG48cD5cdWJjMjlcdWM3NDAgXHViY2ZjXHViODVkIFx1YjJlNFx1YWMwMVx1ZDYxNVx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViNjEwLCBcdWI4NWNcdWJkMDdcdWM3NDAgXHVjMTNjXHVjMTFjXHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWJjYmRcdWM3NDQgXHVjNzc4XHVjMmRkXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Yjg1Y1x1YmQwN1x1Yzc0MCBcdWM3OTBcdWMyZTBcdWM3NzQgXHViZDgwXHViNTJhXHVjZTVjIFx1YmNiZFx1YjljYyBcdWM3NzhcdWMyZGRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWJjYmRcdWM3NDQgXHViYWE4XHViNDUwIFx1Yzc3OFx1YzJkZFx1ZDU1OFx1YjgyNFx1YmE3NCBcdWI4NWNcdWJkMDdcdWM3NDAgXHViYzI5XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWJhYThcdWI0ZTAgXHViY2JkXHVjNWQwIFx1YmQ4MFx1YjUyYVx1Y2NkMFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmNiZCBOXHVhYzFjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWJjMjkoXHViY2ZjXHViODVkIFx1YjJlNFx1YWMwMVx1ZDYxNSlcdWFjZmMgXHViODVjXHViZDA3XHVjNzU4IFx1YzJkY1x1Yzc5MSBcdWM3MDRcdWNlNTggUFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHViYWE4XHViNGUwIFx1YmNiZFx1YzVkMCBcdWJkODBcdWI1MmFcdWNlNWMgXHViMmU0XHVjNzRjLCBcdWIyZTRcdWMyZGMgUFx1Yjg1YyBcdWIzY2NcdWM1NDRcdWM2MjRcdWIyOTQgXHVhYzAwXHVjN2E1IFx1YzllN1x1Yzc0MCBcdWFjYmRcdWI4NWNcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YWYyZFx1YzlkM1x1YzgxMFx1YzVkMCBcdWI4NWNcdWJkMDdcdWM3NzQgXHViZDgwXHViNTJhXHVjZTVjIFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWI0NTAgXHViY2JkXHVjNWQwIFx1YmQ4MFx1YjUyYVx1Y2U1YyBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAmbmJzcDtcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NTggXHVhZjJkXHVjOWQzXHVjODEwIFx1YWMxY1x1YzIxOCBOICgzICZsZTsgTiAmbGU7IDEwMClcdWFjZmMgXHViODVjXHViZDA3XHVjNzU4IFx1YzJkY1x1Yzc5MSBcdWM3MDRcdWNlNTggUHhcdWM2NDAgUHlcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoLTEwLDAwMCAmbGU7IFB4LCBQeSAmbGU7IDEwLDAwMCkgXHViMmU0XHVjNzRjIE5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YmNiZFx1Yzc1OCBcdWFmMmRcdWM5ZDNcdWM4MTAgeCwgeSAoLTEwLDAwMCAmbGU7IHgsIHkgJmxlOyAxMCwwMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhZjJkXHVjOWQzXHVjODEwXHVjNzU4IFx1YzIxY1x1YzExY1x1YjI5NCBcdWJjMThcdWMyZGNcdWFjYzRcdWJjMjlcdWQ1YTUgXHVjNzc0XHVhY2UwLCBcdWJhYThcdWI0ZTAgXHViMGI0XHViZDgwXHVhYzAxXHVjNzQwIDE4MFx1YjNjNFx1YmNmNFx1YjJlNCBcdWM3OTFcdWIyZTQuIFx1YjJlNFx1YWMwMVx1ZDYxNVx1Yzc0MCBcdWFkNTBcdWNjMjhcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNzNjXHViYTcwLCBcdWI4NWNcdWJkMDdcdWM3NTggXHVjMmRjXHVjNzkxIFx1YzcwNFx1Y2U1OFx1YjI5NCBcdWIyZTRcdWFjMDFcdWQ2MTUgXHViMGI0XHViZDgwXHVjNWQwIFx1Yzc4OFx1YjJlNC4gKFx1YjJlNFx1YWMwMVx1ZDYxNSBcdWJjYzAgXHVjNzA0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNWM2XHViMmU0KTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0IFx1YjljOFx1YjJlNCwgXHVjZjAwXHVjNzc0XHVjMmE0IFx1YmM4OFx1ZDYzOFx1YzY0MCBcdWNkNWNcdWIyZTggXHVhY2JkXHViODVjXHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyZuYnNwO1x1YzE4Y1x1YzIxOFx1YzgxMCBcdWMxNGJcdWM5ZjggXHVjNzkwXHViOWFjXHVjNWQwXHVjMTFjIFx1YmMxOFx1YzYyY1x1YjliY1x1ZDU3NFx1YzExYyZuYnNwO1x1YzE4Y1x1YzIxOFx1YzgxMCBcdWI0NThcdWM5ZjhcdWM3OTBcdWI5YWNcdWFlNGNcdWM5YzAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjQyMTAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJSb29tIFNlcnZpY2UiLCJkZXNjcmlwdGlvbiI6IjxwPllvdSBhcmUgd29ya2luZyBmb3IgYSBjb21wYW55IGRlc2lnbmluZyBjdXRlLCBmdW5ueSByb2JvdCB2YWN1dW0gY2xlYW5lcnMuIEF0IGEgaGlnaCBsZXZlbCwgdGhlIHJvYm90cyZyc3F1bzsgYmVoYXZpb3IgaXMgZGl2aWRlZCBpbnRvIHRocmVlIG1vZGVzOjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPkV4cGxvcmF0aW9uPFwvbGk+XHJcblx0PGxpPlZhY3V1bWluZzxcL2xpPlxyXG5cdDxsaT5SYW1wYW50IEtpbGxpbmc8XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5VbmZvcnR1bmF0ZWx5LCB3aGlsZSBjb25zdW1lciB0ZXN0aW5nIHNob3dzIHRoYXQgdGhlIGxhc3QgdHdvIG1vZGVzIGFyZSB3b3JraW5nIHBlcmZlY3RseSwgdGhlIGV4cGxvcmF0aW9uIG1vZGUgc3RpbGwgaGFzIGJ1Z3MuIFlvdSZyc3F1bzt2ZSBiZWVuIHB1dCBpbiBjaGFyZ2Ugb2YgZGVidWdnaW5nLjxcL3A+XHJcblxyXG48cD5BdCB0aGUgYmVnaW5uaW5nIG9mIHRoZSBleHBsb3JhdGlvbiBtb2RlLCB0aGUgcm9ib3QgaXMgcGxhY2VkIGludG8gYSBjb252ZXggcG9seWdvbmFsIHJvb20uIEl0IGhhcyBzZW5zb3JzIHRoYXQgc2hvdWxkIHRlbGwgaXQgd2hlcmUgYWxsIHRoZSB3YWxscyBhcmUuIFlvdXIgam9iIGlzIHRvIHdyaXRlIGEgcHJvZ3JhbSB0aGF0IHZlcmlcdWZiMDFlcyB0aGF0IHRoZXNlIHJlYWRpbmdzIGFyZSBjb3JyZWN0LiBUbyBkbyB0aGlzLCB0aGUgcm9ib3QgbmVlZHMgdG8gcGh5c2ljYWxseSB0b3VjaCBldmVyeSB3YWxsIGluIHRoZSByb29tLjxcL3A+XHJcblxyXG48cD5Zb3VyIHByb2JsZW0gaXMgdGhpczogZ2l2ZW4gdGhlIHNoYXBlIG9mIGEgY29udmV4IHBvbHlnb25hbCByb29tIHdpdGggTiB3YWxscyBhbmQgYSBzdGFydGluZyBwb2ludCBQIGluc2lkZSBpdCwgZGV0ZXJtaW5lIHRoZSBzaG9ydGVzdCByb3V0ZSB0aGF0IHRvdWNoZXMgZWFjaCB3YWxsIGFuZCB0aGVuIHJldHVybnMgdG8gUC4gVG91Y2hpbmcgYSBjb3JuZXIgY291bnRzIGFzIHRvdWNoaW5nIGJvdGggaW5jaWRlbnQgd2FsbHMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5FYWNoIHRlc3QgY2FzZSBzdGFydHMgd2l0aCBhIGxpbmUgY29udGFpbmluZyB0aGUgbnVtYmVyIG9mIHZlcnRpY2VzIE4gb2YgdGhlIHBvbHlnb24gKDMgJmxlOyBOICZsZTsgMTAwKSBhbmQgdGhlIGludGVnZXIgY29vcmRpbmF0ZXMgUHggYW5kIFB5IG9mIHRoZSByb2JvdCZyc3F1bztzIHN0YXJ0aW5nIHBvaW50ICgtMTAgMDAwICZsZTsgUHgsIFB5ICZsZTsgMTAgMDAwKS4gVGhpcyBpcyBmb2xsb3dlZCBieSBOIGxpbmVzLCBlYWNoIGNvbnRhaW5pbmcgdHdvIGludGVnZXJzIHgsIHkgKC0xMCAwMDAgJmxlOyB4LCB5ICZsZTsgMTAgMDAwKSBkZWZpbmluZyBhIHZlcnRleCBvZiB0aGUgcG9seWdvbi4gVmVydGljZXMgYXJlIGdpdmVuIGluIGNvdW50ZXJjbG9ja3dpc2Ugb3JkZXIsIGFsbCBpbnRlcmlvciBhbmdsZXMgYXJlIGxlc3MgdGhhbiAxODAgZGVncmVlcywgdGhlIHBvbHlnb24gZG9lcyBub3Qgc2VsZi1pbnRlcnNlY3QsIGFuZCB0aGUgcm9ib3QmIzM5O3Mgc3RhcnRpbmcgcG9pbnQgaXMgc3RyaWN0bHkgaW5zaWRlIHRoZSBwb2x5Z29uLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgZGlzcGxheSB0aGUgY2FzZSBudW1iZXIgYW5kIHRoZSBsZW5ndGggb2YgdGhlIGRlc2lyZWQgcm91dGUsIGFjY3VyYXRlIHRvIHR3byBkZWNpbWFsIHBsYWNlcy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

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