만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

펀칭 파워

시간 제한2초메모리 제한512 MB

요약
주어진 격자점 중 두 점 사이 거리가 항상 1.3미터를 넘도록 가장 많은 점을 고른다.
난이도

보통10점 중 6점

유형
그래프, 그리디, 기하, 완전 탐색
정답자
아직 제출이 없습니다

문제

공원 관리소가 공원 여기저기에 복싱 머신을 설치하기로 했다. 그동안 기구가 모자랐던 만큼 이번에는 가능한 한 많이 놓으려고 한다. 그래도 공원이 기계로 가득 차지는 않는다. 설치 자리에 걸린 법적 제한이 꽤 까다롭기 때문이다.

관리소는 복싱 머신을 놓을 수 있는 자리를 모두 공원 도면에 표시하고 좌표를 적어 두었다. 제조사의 안전 규정도 지켜야 한다. 복싱 머신 두 대 사이의 거리는 언제나 1.31.3미터 이상이다.

규정을 지키면서 설치할 수 있는 복싱 머신의 최대 개수를 구하라.

입력

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 공원에서 복싱 머신을 놓을 수 있는 자리의 수 NN이 주어진다 (1≤N≤20001 \le N \le 2000). 이어지는 NN개의 줄에는 자리마다 좌표가 정수 두 개로 주어진다. 단위는 미터이고, 각 좌표는 00 이상 10910^9 이하다. 한 테스트 케이스 안에서 같은 좌표가 두 번 나오지 않는다.

한 테스트 케이스의 자리들은 전체가 하나로 이어져 있다. 어느 자리에서 출발하든, 한 번에 좌표 하나만 11씩 바꾸고 복싱 머신을 놓을 수 있는 자리만 밟으면서 나머지 모든 자리에 도달할 수 있다.

테스트 케이스는 최대 100100개이고, 모든 테스트 케이스의 NN을 합한 값은 2000020000 이하다. 입력은 파일의 끝에서 끝난다.

출력

각 테스트 케이스마다 설치할 수 있는 복싱 머신의 최대 개수를 한 줄에 하나씩 출력한다.

예제4

  1. 예제 1

    입력
    4
0 0
0 1
1 0
1 1
6
0 1
1 0
1 1
1 2
1 3
2 2
    예상 출력
    2
4

  2. 예제 2

    입력
    1
0 0
    예상 출력
    1

  3. 예제 3

    입력
    2
0 0
1 0
2
5 7
5 8
5
3 3
3 4
2 4
4 4
3 5
    예상 출력
    1
1
4

  4. 예제 4

    입력
    100
0 0
1 0
1 1
2 1
2 2
3 2
3 3
4 3
4 4
5 4
5 5
6 5
6 6
7 6
7 7
8 7
8 8
9 8
9 9
10 9
10 10
11 10
11 11
12 11
12 12
13 12
13 13
14 13
14 14
15 14
15 15
16 15
16 16
17 16
17 17
18 17
18 18
19 18
19 19
20 19
20 20
21 20
21 21
22 21
22 22
23 22
23 23
24 23
24 24
25 24
25 25
26 25
26 26
27 26
27 27
28 27
28 28
29 28
29 29
30 29
30 30
31 30
31 31
32 31
32 32
33 32
33 33
34 33
34 34
35 34
35 35
36 35
36 36
37 36
37 37
38 37
38 38
39 38
39 39
40 39
40 40
41 40
41 41
42 41
42 42
43 42
43 43
44 43
44 44
45 44
45 45
46 45
46 46
47 46
47 47
48 47
48 48
49 48
49 49
50 49
    예상 출력
    50