Under construction

Still being built. Things may change

Punching Power

Time limit2sMemory limit512 MB

Summary
Choose the largest subset of given grid points so every pair is more than 1.3 meters apart.
Level

Medium6 of 10

Topics
Graph, Greedy, Geometry, Brute force
Solved
No attempts yet

Problem

The park management decided to install boxing machines at several places in the park. Machines have been in short supply, so this time they want to put up as many as they can. The park will still not fill up with machines, because the legal limits on where a machine may stand are strict.

The management marked every possible machine position on the park plan and wrote down its coordinates. The manufacturer's safety rule applies as well. The distance between any two boxing machines is at least 1.31.3 meters.

Find the largest number of boxing machines that can be installed without breaking that rule.

Input

The input holds several test cases. The first line of each test case has one integer NN, the number of possible machine positions in the park (1≤N≤20001 \le N \le 2000). Each of the next NN lines describes one position with two integer coordinates in meters. Every coordinate is at least 00 and at most 10910^9. The same coordinate pair never appears twice inside one test case.

The positions of one test case form a single connected group. Starting from any position you can reach every other position by steps that change exactly one coordinate by 11 and always land on a position where a machine may stand.

There are at most 100100 test cases, and the sum of NN over all test cases is at most 2000020000. The input ends at end of file.

Output

For each test case, print one line with the largest number of boxing machines that can be installed.

Examples4

  1. Example 1

    Input
    4
0 0
0 1
1 0
1 1
6
0 1
1 0
1 1
1 2
1 3
2 2
    Expected output
    2
4

  2. Example 2

    Input
    1
0 0
    Expected output
    1

  3. Example 3

    Input
    2
0 0
1 0
2
5 7
5 8
5
3 3
3 4
2 4
4 4
3 5
    Expected output
    1
1
4

  4. Example 4

    Input
    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
    Expected output
    50