← 返回 google 的题目列表Count Clusters of 2D Points Within Radius
类型：online_judge
Problem: Count Clusters of 2D Points Within Radius
Given n points on a 2D plane and a radius r, two points are considered directly connected if their Euclidean distance is <= r.
Connectivity is transitive: if point A is connected to point B, and point B is connected to point C, then A, B, and C belong to the same cluster.
Return the total number of clusters.
Input Format
The first line contains two integers:
n r
where:
n is the number of points
r is the connection radius
The next n lines each contain two integers:
x_i y_i
representing the coordinates of the i-th point.
Output Format
Print one integer: the number of clusters.
Constraints
1 <= n <= 2000
0 <= r <= 10^9
-10^9 <= x_i, y_i <= 10^9
Duplicate points may exist
Distance is Euclidean distance
Example 1
Input:
3 1
0 0
1 0
3 0
Output:
2
Explanation: (0,0) and (1,0) have distance 1, so they are in the same cluster. (3,0) forms another cluster.
Example
Input
3 1
0 0
1 0
3 0
Output
2