시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHJcblxyXG48cD5cdWJjMjlcdWM3NDAgXHViY2ZjXHViODVkIFx1YjJlNFx1YWMwMVx1ZDYxNVx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViNjEwLCBcdWI4NWNcdWJkMDdcdWM3NDAgXHVjMTNjXHVjMTFjXHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWJjYmRcdWM3NDQgXHVjNzc4XHVjMmRkXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Yjg1Y1x1YmQwN1x1Yzc0MCBcdWM3OTBcdWMyZTBcdWM3NzQgXHViZDgwXHViNTJhXHVjZTVjIFx1YmNiZFx1YjljYyBcdWM3NzhcdWMyZGRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWJjYmRcdWM3NDQgXHViYWE4XHViNDUwIFx1Yzc3OFx1YzJkZFx1ZDU1OFx1YjgyNFx1YmE3NCBcdWI4NWNcdWJkMDdcdWM3NDAgXHViYzI5XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWJhYThcdWI0ZTAgXHViY2JkXHVjNWQwIFx1YmQ4MFx1YjUyYVx1Y2NkMFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmNiZCBOXHVhYzFjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWJjMjkoXHViY2ZjXHViODVkIFx1YjJlNFx1YWMwMVx1ZDYxNSlcdWFjZmMgXHViODVjXHViZDA3XHVjNzU4IFx1YzJkY1x1Yzc5MSBcdWM3MDRcdWNlNTggUFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHViYWE4XHViNGUwIFx1YmNiZFx1YzVkMCBcdWJkODBcdWI1MmFcdWNlNWMgXHViMmU0XHVjNzRjLCBcdWIyZTRcdWMyZGMgUFx1Yjg1YyBcdWIzY2NcdWM1NDRcdWM2MjRcdWIyOTQgXHVhYzAwXHVjN2E1IFx1YzllN1x1Yzc0MCBcdWFjYmRcdWI4NWNcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YWYyZFx1YzlkM1x1YzgxMFx1YzVkMCBcdWI4NWNcdWJkMDdcdWM3NzQgXHViZDgwXHViNTJhXHVjZTVjIFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWI0NTAgXHViY2JkXHVjNWQwIFx1YmQ4MFx1YjUyYVx1Y2U1YyBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAmbmJzcDtcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NTggXHVhZjJkXHVjOWQzXHVjODEwIFx1YWMxY1x1YzIxOCBOICgzICZsZTsgTiAmbGU7IDEwMClcdWFjZmMgXHViODVjXHViZDA3XHVjNzU4IFx1YzJkY1x1Yzc5MSBcdWM3MDRcdWNlNTggUHhcdWM2NDAgUHlcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoLTEwLDAwMCAmbGU7IFB4LCBQeSAmbGU7IDEwLDAwMCkgXHViMmU0XHVjNzRjIE5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YmNiZFx1Yzc1OCBcdWFmMmRcdWM5ZDNcdWM4MTAgeCwgeSAoLTEwLDAwMCAmbGU7IHgsIHkgJmxlOyAxMCwwMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhZjJkXHVjOWQzXHVjODEwXHVjNzU4IFx1YzIxY1x1YzExY1x1YjI5NCBcdWJjMThcdWMyZGNcdWFjYzRcdWJjMjlcdWQ1YTUgXHVjNzc0XHVhY2UwLCBcdWJhYThcdWI0ZTAgXHViMGI0XHViZDgwXHVhYzAxXHVjNzQwIDE4MFx1YjNjNFx1YmNmNFx1YjJlNCBcdWM3OTFcdWIyZTQuIFx1YjJlNFx1YWMwMVx1ZDYxNVx1Yzc0MCBcdWFkNTBcdWNjMjhcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNzNjXHViYTcwLCBcdWI4NWNcdWJkMDdcdWM3NTggXHVjMmRjXHVjNzkxIFx1YzcwNFx1Y2U1OFx1YjI5NCBcdWIyZTRcdWFjMDFcdWQ2MTUgXHViMGI0XHViZDgwXHVjNWQwIFx1Yzc4OFx1YjJlNC4gKFx1YjJlNFx1YWMwMVx1ZDYxNSBcdWJjYzAgXHVjNzA0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNWM2XHViMmU0KTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0IFx1YjljOFx1YjJlNCwgXHVjZjAwXHVjNzc0XHVjMmE0IFx1YmM4OFx1ZDYzOFx1YzY0MCBcdWNkNWNcdWIyZTggXHVhY2JkXHViODVjXHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWMxOGNcdWMyMThcdWM4MTAgXHViNDU4XHVjOWY4XHVjNzkwXHViOWFjXHVhZTRjXHVjOWMwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI0MjEwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUm9vbSBTZXJ2aWNlIiwiZGVzY3JpcHRpb24iOiI8cD5Zb3UgYXJlIHdvcmtpbmcgZm9yIGEgY29tcGFueSBkZXNpZ25pbmcgY3V0ZSwgZnVubnkgcm9ib3QgdmFjdXVtIGNsZWFuZXJzLiBBdCBhIGhpZ2ggbGV2ZWwsIHRoZSByb2JvdHMmcnNxdW87IGJlaGF2aW9yIGlzIGRpdmlkZWQgaW50byB0aHJlZSBtb2Rlczo8XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5FeHBsb3JhdGlvbjxcL2xpPlxyXG5cdDxsaT5WYWN1dW1pbmc8XC9saT5cclxuXHQ8bGk+UmFtcGFudCBLaWxsaW5nPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+VW5mb3J0dW5hdGVseSwgd2hpbGUgY29uc3VtZXIgdGVzdGluZyBzaG93cyB0aGF0IHRoZSBsYXN0IHR3byBtb2RlcyBhcmUgd29ya2luZyBwZXJmZWN0bHksIHRoZSBleHBsb3JhdGlvbiBtb2RlIHN0aWxsIGhhcyBidWdzLiBZb3UmcnNxdW87dmUgYmVlbiBwdXQgaW4gY2hhcmdlIG9mIGRlYnVnZ2luZy48XC9wPlxyXG5cclxuPHA+QXQgdGhlIGJlZ2lubmluZyBvZiB0aGUgZXhwbG9yYXRpb24gbW9kZSwgdGhlIHJvYm90IGlzIHBsYWNlZCBpbnRvIGEgY29udmV4IHBvbHlnb25hbCByb29tLiBJdCBoYXMgc2Vuc29ycyB0aGF0IHNob3VsZCB0ZWxsIGl0IHdoZXJlIGFsbCB0aGUgd2FsbHMgYXJlLiBZb3VyIGpvYiBpcyB0byB3cml0ZSBhIHByb2dyYW0gdGhhdCB2ZXJpXHVmYjAxZXMgdGhhdCB0aGVzZSByZWFkaW5ncyBhcmUgY29ycmVjdC4gVG8gZG8gdGhpcywgdGhlIHJvYm90IG5lZWRzIHRvIHBoeXNpY2FsbHkgdG91Y2ggZXZlcnkgd2FsbCBpbiB0aGUgcm9vbS48XC9wPlxyXG5cclxuPHA+WW91ciBwcm9ibGVtIGlzIHRoaXM6IGdpdmVuIHRoZSBzaGFwZSBvZiBhIGNvbnZleCBwb2x5Z29uYWwgcm9vbSB3aXRoIE4gd2FsbHMgYW5kIGEgc3RhcnRpbmcgcG9pbnQgUCBpbnNpZGUgaXQsIGRldGVybWluZSB0aGUgc2hvcnRlc3Qgcm91dGUgdGhhdCB0b3VjaGVzIGVhY2ggd2FsbCBhbmQgdGhlbiByZXR1cm5zIHRvIFAuIFRvdWNoaW5nIGEgY29ybmVyIGNvdW50cyBhcyB0b3VjaGluZyBib3RoIGluY2lkZW50IHdhbGxzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+RWFjaCB0ZXN0IGNhc2Ugc3RhcnRzIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgdGhlIG51bWJlciBvZiB2ZXJ0aWNlcyBOIG9mIHRoZSBwb2x5Z29uICgzICZsZTsgTiAmbGU7IDEwMCkgYW5kIHRoZSBpbnRlZ2VyIGNvb3JkaW5hdGVzIFB4IGFuZCBQeSBvZiB0aGUgcm9ib3QmcnNxdW87cyBzdGFydGluZyBwb2ludCAoLTEwIDAwMCAmbGU7IFB4LCBQeSAmbGU7IDEwIDAwMCkuIFRoaXMgaXMgZm9sbG93ZWQgYnkgTiBsaW5lcywgZWFjaCBjb250YWluaW5nIHR3byBpbnRlZ2VycyB4LCB5ICgtMTAgMDAwICZsZTsgeCwgeSAmbGU7IDEwIDAwMCkgZGVmaW5pbmcgYSB2ZXJ0ZXggb2YgdGhlIHBvbHlnb24uIFZlcnRpY2VzIGFyZSBnaXZlbiBpbiBjb3VudGVyY2xvY2t3aXNlIG9yZGVyLCBhbGwgaW50ZXJpb3IgYW5nbGVzIGFyZSBsZXNzIHRoYW4gMTgwIGRlZ3JlZXMsIHRoZSBwb2x5Z29uIGRvZXMgbm90IHNlbGYtaW50ZXJzZWN0LCBhbmQgdGhlIHJvYm90JiMzOTtzIHN0YXJ0aW5nIHBvaW50IGlzIHN0cmljdGx5IGluc2lkZSB0aGUgcG9seWdvbi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIGRpc3BsYXkgdGhlIGNhc2UgbnVtYmVyIGFuZCB0aGUgbGVuZ3RoIG9mIHRoZSBkZXNpcmVkIHJvdXRlLCBhY2N1cmF0ZSB0byB0d28gZGVjaW1hbCBwbGFjZXMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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