[BOJ 1098] 쌍둥이 마을

View as PDF

Submit solution

Points: 4
Time limit: 2.0s
Memory limit: 128M

Problem types
Allowed languages
Assembly, Awk, C, C++, Java, Pascal, Perl, Python, Sed, Text

쌍둥이 마을은 두 마을의 사람들 간에 커뮤니케이션과 문화적 교류를 위해서 만든 것이다.</p>

따라서 정부는 마을 사이에 쌍둥이 마을을 많이 제정하려고 한다. 물론 가능한 모든 마을의 쌍을 쌍둥이 마을로 제정하면 좋겠지만, 다음과 같은 규칙을 지켜야 한다.

  1. 각 마을은 P개 이하의 쌍둥이 마을을 가진다. 쌍둥이 마을이 없을 수도 있다.
  2. 각 쌍둥이 마을의 거리는 적어도 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

There are no comments at the moment.