Codah ClubTrain. Submit. Improve.
Sign in
English
#00013D

z-radars

Little Z. gained a control of N radar stations. Each of the radar stations are on the field, and its position can be represented with x,y coordinates (in arbitrary units). Each of the radars, can communicate with all the radars that are not more than R units away.

For security reasons, you have group the radar stations into groups so that each group has the following property:

If you block signal from one radar to some other radar from the same group, there has to be some way for these two radars to communicate through the radars from the same group.

The groups might contain only one radar! They can have one or more radars.

But you should optimize the total number of groups, the number of groups should be minimal.



For given locations of the radars, and the range of the radars R, find the number of groups that have the property described above


InputFrom the first line of the standard input read two integers N and R, where (1 <= N <= 5000) is the number of radars, and ( 1 <= R <= 2000000) is the range of each of the radars. From each of the next N lines read two integers representing the x and y coordinates of the corresponding radar. Both x and y will be in the range [0, 2000000].

OutputTo the standard output write one integer representing the minimal number of groups with the property described in the problem

Input:
6 3
1 1
1 2
2 2
10 10
11 11
11 10
Output:
2

Input:
4 2
1 1
2 2
3 3
4 4Output:
4
Explanation: In this case, the groups are the single radars!

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.