算法题：对相交的圆进行分组（python）

# -*- coding: utf-8 -*-
# 相交的圆
'''
问题2:假定二维空间平面内有n个圆,现在我们需要将存在`交集`的圆进行分组,输出结果为n个组,每个组包含i个圆.  
交集算法: 两圆心的距离 小于 两圆半径之和.  

假设圆数据为: (用数组表示圆)  
[
    { X: 0, Y: 0, Radius: 1 },
    { X: 3, Y: 2, Radius: 2 },
    { X: 2, Y: 1, Radius: 3 },
    { X: 5, Y: 2, Radius: 4 },
    { X: 1, Y: 3, Radius: 5 },
    { X: 2, Y: 4, Radius: 6 },
    { X: 2323, Y: 121, Radius: 7 },
    { X: 2323, Y: 121, Radius: 7 },
    { X: 2322, Y: 121, Radius: 7 },
]

那么输出的结果为:  
```json
​​​​​[ [ { X: 0, Y: 0, Radius: 1 },​​​​​
​​​​​    { X: 2, Y: 1, Radius: 3 },​​​​​
​​​​​    { X: 1, Y: 3, Radius: 5 },​​​​​
​​​​​    { X: 2, Y: 4, Radius: 6 },​​​​​
​​​​​    { X: 3, Y: 2, Radius: 2 },​​​​​
​​​​​    { X: 5, Y: 2, Radius: 4 } ],​​​​​
​​​​​  [ { X: 2323, Y: 121, Radius: 7 },​​​​​
​​​​​    { X: 2323, Y: 121, Radius: 7 },​​​​​
​​​​​    { X: 2322, Y: 121, Radius: 7 } ] ]​​​​​
```

假设代码结构为如下:  


```json
    { X: 1, Y: 0.7, Radius: 0.6 },
    { X: 0, Y: 0, Radius: 0.6 },
    { X: 1, Y: 0, Radius: 0.5 },
```

//圆1和圆2并不交集.  
//圆2和圆3存在交集  
//圆1和圆3存在交集  

//那么结果为  
[cir1,cir2,cir3]//他们应该是一组的.  
'''

class Circle(object):
    def __init__(self, x,y,radius):
        self.x=x
        self.y=y
        self.radius=radius
        self.flag=0

def groupCirclesByIntersect(cirs):
    def getDist(c1, c2):
        return pow(pow(c1.x-c2.x, 2) + pow(c1.y-c2.y, 2), 0.5)


    ans=[]
    for x in cirs:
        if x.flag:continue
        x.flag=1
        group=[x]
        stack=[x]
        while stack:
            c1=stack.pop()
            for c2 in cirs:
                if c2.flag==0 and getDist(c1,c2) < c1.radius+c2.radius:
                    c2.flag=1
                    group.append(c2)
                    stack.append(c2)
        ans.append(group)
    return ans

if __name__ == '__main__':
    inputs = [
        Circle(0, 0, 1),
        Circle(3, 2, 2),
        Circle(2, 1, 3),
        Circle(5, 2, 4),
        Circle(1, 3, 5),
        Circle(2, 4, 6),
        Circle(2323, 121, 7),
        Circle(2323, 121, 7),
        Circle(2322, 121, 7),
        # Circle(1, 0.7, 0.6),
        # Circle(0, 0, 0.6),
        # Circle(1, 0, 0.5),
    ]
    groups=groupCirclesByIntersect(inputs)
    print map(lambda x: [(e.x,e.y,e.radius)for e in x], groups)