4210번 - 로봇 청소기 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 | 128 MB | 40 | 8 | 7 | 36.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
출처
ICPC > World Finals > ACM-ICPC World Finals 2012 H번
- 문제를 번역한 사람: baekjoon
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호