시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 1 0 0 0.000%

문제

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

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

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

벽 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도보다 작다. 다각형은 교차하지 않으며, 로봇의 시작 위치는 다각형 내부에 있다. (다각형 변 위에 있는 경우는 없다)

출력

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

예제 입력

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

예제 출력

Case 1: 5.66
Case 2: 36.73

힌트

출처

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