[BOJ 1098] 쌍둥이 마을
View as PDF
Submit solution
Assembly, Awk, C, C++, Java, Pascal, Perl, Python, Sed, Text
Points:
4
Time limit:
2.0s
Memory limit:
128M
Problem types
Allowed languages
쌍둥이 마을은 두 마을의 사람들 간에 커뮤니케이션과 문화적 교류를 위해서 만든 것이다.</p>
따라서 정부는 마을 사이에 쌍둥이 마을을 많이 제정하려고 한다. 물론 가능한 모든 마을의 쌍을 쌍둥이 마을로 제정하면 좋겠지만, 다음과 같은 규칙을 지켜야 한다.
- 각 마을은 P개 이하의 쌍둥이 마을을 가진다. 쌍둥이 마을이 없을 수도 있다.
- 각 쌍둥이 마을의 거리는 적어도 D이다.두 마을이 (x1, y1) 과 (x2, y2) 에 있을 때, 두 마을 사이의 거리는 |x1-x2| + |y1-y2|이다.
정부는 되도록이면 많은 쌍둥이 마을을 만들려고 한다. 만약 이러한 것이 여러 가지라면, 쌍둥이 마을 사이의 거리의 합을 최소로하는 것을 선택한다. 각 마을의 위치와 P와 D가 주어질 때, 쌍둥이 마을의 개수의 최댓값과 그 때 쌍둥이 마을 사이의 거리의 합을 구하는 프로그램을 작성하시오.
입력 형식
첫째 줄에 마을의 개수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 마을의 좌표가 주어진다. x좌표와 y좌표 순서대로 주어지며, 각 좌표는 1,000보다 작거나 같은 자연수 또는 0이다. 마지막 줄에는 P와 D가 주어진다. P는 3보다 작거나 같은 자연수이고, D는 2,000보다 작거나 같은 자연수이다. 두 도시의 위치가 중복되는 경우는 없다.
출력 형식
첫째 줄에 문제의 정답을 출력한다.
예제 입력 1
3
0 0
0 10
10 4
1 11
예제 출력 1
1 14
예제 입력 2
3
0 0
0 10
10 4
1 1
예제 출력 2
1 10
예제 입력 3
4
0 0
10 0
0 20
10 20
1 1
예제 출력 3
2 20
예제 입력 4
4
0 0
10 0
0 20
10 20
2 10
예제 출력 4
4 60
예제 입력 5
9
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
3 6
예제 출력 5
6 40
Comments