9128번 - 피곤한 외판원 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 62 | 2 | 2 | 25.000% |
문제
오랜 시간 동안 여행해오던 외판원은 너무 피곤해져서 이제 한 곳에 정착하여 집을 세우고 고객들에게 자신의 집에 방문하도록 하려고 한다.
고객이 살고 있는 위치는 정수로 된 x, y 좌표를 가지며, 모든 위치는 서로 다르다. 외판원도 정수 좌표 위에 집을 지어야 하며, 어떤 고객의 집과도 그 위치가 겹쳐서는 안 된다. 또한 각 고객이 외판원의 집을 방문하려면 맨하탄 거리, 즉 외판원의 집 위치가 (x, y)이고 고객의 위치가 (xi, yi)일 때 |x − xi| + |y − yi|만큼을 이동해야 한다.
모든 고객의 이동거리 합이 최소가 되게 하는 위치는 몇 군데나 존재할까?
입력
첫째 줄에 테스트 케이스의 개수 T(≤ 100)가 주어진다.
이어서 각 테스트 케이스마다, 첫째 줄에 고객의 수 n(1 ≤ n ≤ 2 000), 이어서 n개의 줄에 i번째 고객의 위치 xi, yi(−1000000000 ≤ xi,yi ≤ 1000000000)가 주어진다. 모든 값은 정수이다.
출력
각 테스트 케이스마다 모든 고객의 이동거리 합의 최솟값, 그러한 합이 나오게 하는 외판원 집의 위치 개수를 공백으로 구분하여 한 줄에 출력한다.
예제 입력 1
2 4 1 -3 0 1 -2 1 1 -1 2 -999888777 1000000000 1000000000 -987654321
예제 출력 1
10 4 3987543098 3975087573110998514
출처
ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2007 Preliminaries F번
- 문제를 번역한 사람: kks227
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호