3894번 - 지그재그 스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 128 MB | 20 | 0 | 0 | 0.000% |
문제
평면 위에 점이 여러 개 주어진다. 이 점을 모두 지나는 지그재그 선을 찾으려고 한다. 이때, 전환점(turning point)의 개수를 가장 적게 하려고 한다. 또, 전환점의 개수가 같은 경우에는 선의 길이가 가장 작은 것을 찾으려고 한다.
예를 들어, 아래와 같이 평면 위에 점이 9개가 있다고 하자.
지그재그 선은 여러 선분으로 이루어져 있고, 각 선분은 점을 두 개 이상 지나야 한다.
지그재그 선은 선이 꺽일 수 있는데, 이 꺽이는 지점을 전환점(turning point)라고 한다. 전환점은 주어진 점 위에 있을 수도 있고, 아닐 수도 있다.
왼쪽 지그재그 선의 길이: 8 + 3√2 ≃ 12.242641, 오른쪽 지그재그 선의 길이: 2√2 + (6 + 1/2) + 5√5/2 ≃ 14.918597
위의 그림은 주어진 점을 지나는 지그재그 선이고 두 선 모두 전환점의 개수는 3개이다. 왼쪽 지그재그 선의 길이는 오른쪽 지그재그 선의 길이보다 짧다. 또, 왼쪽 지그재그 선은 주어진 아홉 개의 점을 지나는 가장 짧은 지그재그 선이다.
전환점을 네 개 갖는 지그재그 선은 아래와 같다. 이 선의 길이는 위의 그림의 길이보다 짧지만, 전환점의 수가 더 많기 때문에 정답이 아니다.
아래와 같이 점이 7개 있고, 그 점을 잇는 두가지로 이었다고 하자. 이때, 왼쪽의 길이가 오른쪽보다 더 길지만, 정답은 왼쪽 그림이 된다. 그 이유는 지그재그 선의 모든 선분은 점을 두 개 이상 지나야 하기 때문이다.
점이 주어졌을 때, 지그재그 선을 구하는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 점의 개수 n이 주어진다. 다음 n개의 줄에는 점의 좌표가 주어진다.
모든 좌표는 음이 아닌 정수이고, 공백으로 구분되어 있다. n은 2이상 10이하의 자연수이고, x,y좌표는 0이상 10이하의 정수이다. 점의 순서는 별 의미가 없다.
출력
각 테스트 케이스에 대해서, 가장 적은 전환점을 갖는 지그재그 선 중 가장 짧은 것의 전환점의 개수와 길이를 출력한다. 선의 길이는 정답과의 오차가 0.0001까지 허용된다.
가장 적은 전환점의 개수는 최대 4개이며, 따라서 선분의 개수는 최대 5개가 된다.
예제 입력 1
2 0 0 10 9 4 0 0 3 1 0 3 3 3 10 2 2 4 2 6 2 2 4 4 4 6 4 2 6 4 6 6 6 3 3 10 0 0 2 0 4 0 0 2 2 2 4 2 0 4 2 4 4 4 6 8 9 0 0 1 0 3 0 0 1 1 1 3 1 0 2 1 2 2 2 10 0 0 1 0 0 1 1 1 9 9 9 10 10 9 10 10 0 2 10 8 10 0 0 0 10 2 0 2 1 2 7 2 10 5 1 6 7 9 2 10 9 0
예제 출력 1
0 13.45362405 1 18.48683298 3 24.14213562 4 24.94813673 3 12.24264069 3 60.78289622 3 502.7804353
힌트
첫 번째 데이터: 
두 번째 데이터: 
세 번째 데이터: 
네 번째 데이터: 
출처
ICPC > Regionals > Asia Pacific > Japan > Asia Regional Contest 2008 in Aizu J번
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호