PayPal上海团队一直致力于风险控制,风控需要收集各种信息,有时需要通过地理位置找出用户与用户之间存在的关联关系,这一信息可能会用于找出用户潜在存在的风险问题。我们记两个用户的关联关系可以表示为: (1). user1,user2与他们最常发生交易的地理位置分别为(x1, y1),(x2, y2),当这两个用户的欧氏距离不超过d时,我们就认为两个用户关联。 (2). 用户关联性具有传递性,若用户1与用户2关联,用户2与用户3关联,那么用户1,2,3均关联。 给定N个用户及其地理位置坐标,将用户按照关联性进行划分,要求返回一个集合,集合中每个元素是属于同一个范围的用户群。
输入描述:
d:欧式距离N:用户数之后的N行表示第0个用户到第N-1个用户的地理位置坐标


输出描述:
一个数组集合,所有关联的用户在一个数组中。输出数组需要按照从小到大的顺序排序,每个集合内的数组也需要按照从小到大的顺序排序。
示例1

输入

2.0
5
3.0 5.0
6.0 13.0
2.0 6.0
7.0 12.0
0.0 2.0

输出

[[0, 2], [1, 3], [4]]
加载中...