시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
10 초 | 512 MB | 1025 | 305 | 203 | 34.642% |
지뢰제거를 위해서 새로운 장비가 투입되었다. 이 장비를 이용하면 10m × 10m 정사각형 범위 안(경계 포함)에 있는 지뢰를 한꺼번에 제거할 수 있다. 10,000m × 10,000m의 작업장에 묻힌 지뢰의 위치를 모두 알고 있다고 할 때, 이 장치를 효과적으로 사용하기 위해서 한 번 사용하여 제거할 수 있는 최대 지뢰 개수를 계산하는 프로그램을 작성하시오. 위의 그림은 아래 "예제 입력"의 세 번째 경우를 나타낸 것이다. 그림에서 보이는 정사각형 영역에 이 장비를 사용하면 다섯 개의 지뢰를 한꺼번에 제거할 수 있으며, 이 수가 한 번 사용하여 제거할 수 있는 최대 지뢰 개수이다.
입력의 첫 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스는 한 줄에 지뢰의 개수를 나타내는 하나의 정수 N (4 ≤ N ≤ 100,000)이 주어진 다음, N개의 좌표가 한 줄에 하나씩 주어진다. 각 좌표는 0이상 10,000이하의 두 정수로 주어지는데, 첫 번째 정수는 x-좌표를, 두 번째 정수는 y-좌표를 나타낸다. 모든 정수 사이에는 한 칸의 공백이 존재한다. 같은 좌표에 두 개 이상의 지뢰는 존재하지 않으며, 지뢰의 크기는 무시할 정도로 작다고 가정한다.
각 테스트 케이스에 대해서 한 번에 가장 많이 제거할 수 있는 지뢰의 수를 출력한다.
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
2 5 5