시간 제한메모리 제한제출정답맞힌 사람정답 비율
10 초 512 MB102530520334.642%

문제

지뢰제거를 위해서 새로운 장비가 투입되었다. 이 장비를 이용하면 10m × 10m 정사각형 범위 안(경계 포함)에 있는 지뢰를 한꺼번에 제거할 수 있다. 10,000m × 10,000m의 작업장에 묻힌 지뢰의 위치를 모두 알고 있다고 할 때, 이 장치를 효과적으로 사용하기 위해서 한 번 사용하여 제거할 수 있는 최대 지뢰 개수를 계산하는 프로그램을 작성하시오. 위의 그림은 아래 "예제 입력"의 세 번째 경우를 나타낸 것이다. 그림에서 보이는 정사각형 영역에 이 장비를 사용하면 다섯 개의 지뢰를 한꺼번에 제거할 수 있으며, 이 수가 한 번 사용하여 제거할 수 있는 최대 지뢰 개수이다.

입력

입력의 첫 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스는 한 줄에 지뢰의 개수를 나타내는 하나의 정수 N (4 ≤ N ≤ 100,000)이 주어진 다음, N개의 좌표가 한 줄에 하나씩 주어진다. 각 좌표는 0이상 10,000이하의 두 정수로 주어지는데, 첫 번째 정수는 x-좌표를, 두 번째 정수는 y-좌표를 나타낸다. 모든 정수 사이에는 한 칸의 공백이 존재한다. 같은 좌표에 두 개 이상의 지뢰는 존재하지 않으며, 지뢰의 크기는 무시할 정도로 작다고 가정한다. 

출력

각 테스트 케이스에 대해서 한 번에 가장 많이 제거할 수 있는 지뢰의 수를 출력한다.

예제 입력 1

3
4
10 10
20 20
30 30
40 40
15
36 33
15 27
35 43
42 36
21 49
27 12
9 40
26 13
26 40
36 22
18 11
29 17
30 32
23 12
35 17
27
40 10
26 11
6 13
53 15
18 16
23 18
33 16
42 20
10 21
3 27
6 43
13 37
16 27
15 46
23 26
23 49
30 23
30 37
33 47
37 23
40 40
46 48
40 29
43 28
49 25
46 30
44 33

예제 출력 1

2
5
5

출처

ICPC > Regionals > Asia Pacific > Korea > Nationwide Internet Competition > Seoul Nationalwide Internet Competition 2004 C번

  • 데이터를 추가한 사람: lobo_prix
  • 문제의 오타를 찾은 사람: yukariko