首先建立一条扫描线，y轴从下至上扫描

我们会发现，当直线扫过圆的最低点时，进入该圆的区域，扫过最高点则退出 

维护一棵平衡二叉树，记录扫描线当时穿越过的所有圆，在树中的优先级顺序就是它们的坐标，自左向右。
由于所有的圆都不相交，所以这些线段也是不相交的 

圆的最低点，就是“进入圆”的事件
圆的最高点，就是“退出圆”的事件

我们把所有圆的最高点和最低点按y坐标排序，每一个代表一个事件。所以排序后我的得到顺序就是事件发生的先后顺序。y坐标低的先发生，坐标高的后发生

依次扫描每一个事件

如果是进入圆的事件，则看看这个事件对应的点（也就是该圆最低点）是否被当前二叉树中某个线段所包含，如果包含，则该圆一定被覆盖；反之则未被覆盖，必须将该圆插入到二叉树中 

如果是离开圆的事件，则需要将该圆在二叉树中删除

你会发现。圆在扫描线中的相对位置是不会发生变化的，也就是说，二叉树只有在进入圆或离开圆时才会改变结构 

这些线段互不相交，你会发现可以利用二分查找来寻找事件点是否在某条线段之内，或者在拿两个线段之间，这样就给平衡二叉树O(logn)的查找、插入提供可能
删除自然也是O(logn)的，加上事件排序，就是O(nlogn) 

二叉树中的线段互不相交  这是可以使用此方法的前提条件

既然互不相交，我们就可以根据它们的左右关系定一个次序，第一个是最左面的，依次是第二左面，第三左面的.... and so on
先使用二分查找的方法确定
选出中间那一条线段，如果该点落入该线段，则自然已得到结果；否则，必定落在该线段的左面或者右面
如果是左面，则该线段右面的线段必然不可能包含该点；左面类似
这样就可以使用二分查找来确定了

平衡二叉树同样如此



.............整理出来的东西，最好不要再加QQ了，我好不容易清理出来的人数又增加了,sigh......

• Re:........还是发上来吧......... (902) majia001 2006-08-06 08:49:50