레이팅 미적용당신은 귀엽고 재미있는 로봇 청소기를 설계하는 회사에서 일하고 있다. 크게 보면 로봇의 동작은 세 가지 모드로 나뉜다. 1. 탐색 2. 청소 3. 무차별 살육 안타깝게도 소비자 테스트 결과 뒤의 두 모드는 완벽하게 작동하지만, 탐색(exp\(lo- ra\)tion) 모드에는 아직 버그가 있다. 당신이 디버깅을 맡게 되었다. 탐색 모드가 시작되면 로봇은 볼록 다각형 모양의 방에 놓인다. 로봇에는 모든 벽의 위치를 알려 주는 센서가 있다. 당신의 일은 이 측정값이 올바른지 검증하는 프로그램을 작성하는 것이다. 이를 위해 로봇은 방의 모든 벽에 물리적으로 닿아야 한다. 문제는 다음과 같다. \(N\)개의 벽을 가진 볼록 다각형 방의 모양과 그 내부의 시작점 \(P\)가 주어질 때, 모든 벽에 닿고 \(P\)로 돌아오는 최단 경로를 구하시오. 모서리(꼭짓점)에 닿는 것은 그 꼭짓점에 붙은 두 벽 모두에 닿는 것으로 간주한다.
각 테스트 케이스는 다각형의 꼭짓점 수 \(N\) (\(3 \le N \le 100\))과 로봇 시작점의 정수 좌표 \(P_{x}\), \(P_{y}\) (−\(10\,000 \le P_{x}\), \(P_{y} \le 10\,000\))가 있는 줄로 시작한다. 이어서 \(N\)개의 줄에 각각 다각형의 꼭짓점을 정의하는 두 정수 \(x\), \(y\) (−\(10\,000 \le x\), \(y \le 10\,000\))가 주어진다. 꼭짓점은 반시계 방향 순서로 주어지고, 모든 내각은 180도보다 작으며, 다각형은 자기 자신과 교차(se\(lf-in\)tersect)하지 않고, 로봇의 시작점은 다각형의 엄격한 내부에 있다.
각 테스트 케이스마다 케이스 번호와 구하는 경로의 길이를 소수점 아래 둘째 자리까지 정확하게 출력한다.
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