← 返回 google 的题目列表Count Clusters of 2D Points Within a Radius
类型：online_judge
Given n points on a 2D plane and a radius r, two points are directly connected if their Euclidean distance is less than or equal to r.
Connectivity is transitive: if A is connected to B, and B is connected to C, then A, B, and C belong to the same cluster, even if the direct distance between A and C is greater than r.
Return the total number of clusters (connected components).
Input Format
First line: two integers n r, the number of points and the radius.
Next n lines: two integers x y, the coordinates of one point.
Output Format
Print one integer: the number of clusters.
Example 1
Input:
5 2
0 0
1 0
3 0
10 0
11 1
Output:
2
Constraints
1 <= n <= 2,000
0 <= r <= 10^9
-10^9 <= x, y <= 10^9
Implement a brute-force solution first; O(n^2) time is acceptable.
Example
Input
5 2
0 0
1 0
3 0
10 0
11 1
Output
2