3970번 - 안전 구역 스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 165 | 46 | 27 | 25.234% |
문제
연종이는 자신의 마당에 새로운 감시 시스템을 설치하려고 한다.
연종이의 마당에는 N개의 원형 물체가 있다. 감시 시스템의 경계에는 고압 울타리를 설치하려고 한다. 울타리 안의 모든 보안 지역은 연결되어 있어야 한다. 또, 모든 물체는 보안 지역 안에 있어야 한다. 모든 물체는 서로 겹치거나 접하지 않는다. 이때, 울타리의 길이를 최소로 하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수 C (0 ≤ C ≤ 100)가 주어진다. 각 테스트 케이스의 첫째 줄에는 물체의 개수 N (0 < N ≤ 25)이 주어진다. 다음 N개의 줄에는 각 물체를 나타내는 세 개의 숫자 xi, yi, ri가 주어진다. i번째 물체의 중심 좌표는 (xi, yi)이며, 반지름은 ri이다. (|xi|, |yi| ≤ 100, 0 < ri ≤ 100)
출력
각 테스트 케이스에 대해서 모든 물체를 포함하는 울타리 길이의 최솟값을 출력한다. 정답과의 오차는 10-7까지 허용한다.
예제 입력 1
3 3 2 2 1 8 2 1 5 6 1 2 6 4 2 2 4 1 4 2 2 2 6 1 1 5 5 2 1 6 1
예제 출력 1
22.2831853072 17.6761051635 25.4247779608
출처
ICPC > Regionals > Europe > Northwestern European Regional Contest > German Collegiate Programming Contest > GCPC 2011 G번
- 문제를 번역한 사람: baekjoon
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호