2209번 - 버스 터미널 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 | 128 MB | 119 | 35 | 28 | 31.461% |
문제
용인시는 버스 정류장이 N개 있는 버스 노선을 짜려고 한다. 각 버스 정류장은 거리의 모퉁이에 있다. 용인시는 현대적으로 설계된 도시이기 때문에 지리 구조가 정사각형 격자 모양으로 짜여 있다. 우리는 이 버스 정류장들 가운데 두 곳을, 중심지로서 H1, H2라는 이름으로 선택하려고 한다. 중심지를 선택하고 나면, 두 중심지 사이에는 버스가 가는 길이 생기며, 중심지를 제외한 나머지 N-2개의 버스 정류장들은 H1 아니면 H2 중 한 곳(두 중심지 모두와 연결되는 것은 아님.)과 직통하게 될 것이다. 이렇게 버스 노선이 결정된다.
이 문제에서 임의의 두 지점 사이의 거리는, 두 곳을 수평 수직 방향으로만 통행하는 가장 가까운 거리이다. 다시 말해, 위치를 (x, y) 좌표로 표현했을 때, 두 지점 (x1, y1)과 (x2, y2)의 거리는 |x1 - x2| + |y1 - y2|로 정의된다는 뜻이다. 한편, 버스 정류장 A와 B가 같은 중심지 H1과 연결돼 있으면 두 정류장 사이의 거리는 A와 H1 사이의 거리와 H1과 B 사이의 거리의 합이 된다. 그리고 A와 B가 각각 다른 중심지인 H1, H2와 연결돼 있으면 두 정류장 사이의 거리는 A와 H1, H1과 H2, H2와 B 사이의 거리들의 합이 된다.
용인시의 도시 계획부는, 모든 시민이 도시의 모든 구역에 최대한 빨리 도착할 수 있게 하길 원한다. 따라서 도시 계획자들은 버스 정거장들 중, 서로 가장 멀리 떨어져 있는 두 곳 사이의 거리를 최소화할 수 있게끔 중심지 두 곳을 고르려고 한다. 이 거리를 최소화하게 중심지를 고른 뒤, 서로 거리가 가장 먼 두 정류장 사이의 거리를 계산하는 프로그램을 작성하시오.
입력
첫째 줄에는 버스 정류장의 개수인 정수 N(2 ≤ N ≤ 500)이 있다. 그리고 다음 N 개의 줄에는 버스 정류장의 x, y좌표가 있다. (가로 먼저, 다음 세로) 각 좌표들은 5000과 같거나 작은 자연수이다. 정류장들은 모두 서로 다른 위치에 있으며, 겹치는 경우가 없다.
출력
거리가 가장 먼 두 정류장 사이의 거리의 최솟값을 나타내는 자연수 하나를 한 줄에다 출력한다.
예제 입력 1
6 1 7 16 6 12 4 4 4 1 1 11 1
예제 출력 1
20
3번과 4번 정류장을 중심지로 선택하면, 2번과 1번 정류장 사이, 그리고 2번과 5번 정류장 사이가 거리가 가장 멀게 되고 이 때 거리는 20이다. 중심지를 어떤 것을 골라도 가장 먼 정거장 사이의 거리를 20보다 짧게 할 수는 없기 때문에 20이 정답이다.
예제 입력 2
7 7 9 10 9 5 3 1 1 7 2 15 6 17 7
예제 출력 2
25
5번과 6번 정류장을 중심지로 선택하면, 가장 먼 정류장의 쌍은 2번과 7번 정류장이 된다. 그 거리는 25이다. 중심지를 어떤 것을 골라도 가장 먼 정거장 사이의 거리를 25보다 짧게 할 수는 없기 때문에 25가 정답이다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호