国家集训队2007论文集1.高逸涵《与圆有关的

《国家集训队2007论文集1.高逸涵《与圆有关的》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、与圆有关的离散化方法北京市清华附中高逸涵引言：一道经典的问题平面中有N个矩形，求他们的面积并。解决方法：离散化。取每个矩形的上下边界，将平面分为若干部分，然后计算每一部分的面积。引言：新的问题由于矩形的边界为折线，如果我们用折线的转折点作为分界点，则折线被化简为许多线段。所以离散化法取得了成功。如果需要统计的并不是矩形，而是某些曲线图形，怎么办？对于曲线来说，根本没有所谓的转折点，传统的离散化法似乎对这一类问题失效了。而梯形和弓形的面积很容易求出但如果增加一些其他的分割线，我们发现，整个图形由若干梯形和弓

2、形构成。引言：新的问题事实上，如果我们对于划分后每一部分的性质要求不那么严格，划分还是可以继续下去的。如图，图形被划分为5部分，初看特征不明显。圆的离散化算法算法的一般步骤：根据问题将平面中的圆分割成若干区域，使每个区域具有一定简单的粗粒属性。一般可用直线分割。根据属性确定区域内圆的具体算法，计算每个区域中结果。综合每个区域的结果，给出问题的最终答案。圆的离散化算法关键在于保证区域内数据在整体上易于处理。算法应用实例以上便是离散化法在圆的计算几何问题中最基本的应用。而这里将通过两道例题详细说明。[例1]D

3、olphinPool(Tehran2000)[例2]Empirestrikesback(ural1520)DolphinPool(Tehran2000)给定N(N<=20)个圆的圆心坐标(xi,yi)和半径Ri求平面内在圆外的封闭区域的个数。例如：如下四个圆构成一个圆外的封闭区域没有任何两个圆相切，且没有任何一个圆的圆心在另一个圆内。封闭区域初步分析尽管圆的位置有一定的限制，但可能的情况还是很多的，我们希望有一个通用的算法来解决所有情况而不分类讨论，避免增加编程复杂度和错误几率。由于输入输出都是整数，似乎

4、题目对于精度的要求不高，并且坐标的范围较小(x,y<=1000)。于是可以使用一个基于floodfill的算法。基于Floodfill的算法概述在原图中建立点阵。标记所有在圆内的点为已访问。使用深度优先遍历(DFS)求连通块数连通块数减1即为答案可以看到，这个算法的效率和正确性都由点阵的密集程度决定。而对于这道题目的时限来说，这个算法远远不能达到要求，因此我们需要改进算法。第一次离散化考虑点阵中的每一横行，我们发现圆在每一横行上覆盖的一定是一个连续区间。因此，可以仅记录每一个圆在当前横线上覆盖的区间而不记

5、录每个点具体的被覆盖情况。考虑平面内的一条平行于x轴的直线。可以很容易的计算出每一个圆在其上覆盖的区间。第一次离散化——区间合并接下来，将所有的被覆盖区间合并。这一问题需要应用到基本数据结构栈，可以在线性时间复杂度内解决。区间合并完成后，可以得到所有未被覆盖的区间。第一步离散化——图论模型建图，每个未覆盖区间为一个顶点，相邻两条横线上的区间如果相交，则在它们之间连一条边。然后判断在建成的图中有多少个连通块。判断图中的连通块数量可以使用按层次遍历的方式减少空间需求。仍存在的问题经过初步的离散化，上述算法的正

6、确性和速度都有很大提高。但由于ACM竞赛要求程序必须通过全部数据，而该算法对于某些极限数据的精度仍不能令人满意，因此还有进一步改进算法的必要。第二次离散化仔细观察程序的运行，我们发现它似乎作了许多无用的工作，如下图：我们一眼可知，下图中所有的区间同属于同一连通块。但是我们的程序却为了得到这一结果在不断的迭代。于是，我们有了一个新的想法：跳过无用的横行。第二次离散化事实上，区间之间的继承关系在大多数时候并没有发生改变，仅在少数时刻才会有所改动：一个圆新出现时，将一个区间分为两半。一个圆最下端，两个区间合并为

7、一个。两圆相交，一个区间逐渐减小直至消失。两圆相交，一个新的区间生成。这样，我们可以求出所有的点事件，并模拟区间的生长消亡，从而求出最终答案。但是，如果完全按照上述想法编程实现，编程复杂度非常高。事实上，我们可以考虑一种懒惰的实现方式。第二次离散化——图示点事件小结至此，本题已被完美解决，时间复杂度为O(N3)。回顾我们得到算法的步骤：根据题目描述得到一种简单的算法。通过离散化不断将其时间复杂度降低，并将精度提高。可以看到，使用了离散化法后，我们轻易地得到了一个简单而优秀的算法。例2Empirestrik

8、esback(ural1520)平面中有1个大圆和N(N<=300)个小圆，大圆圆心为(0,0)，小圆圆心都在大圆内。所有小圆半径相同。求使所有小圆能覆盖整个大圆的小圆最小半径。初步分析由于题目仅需求出一个实数，因此我们考虑使用二分法求得答案。在已知小圆半径的情况下，我们所需要做的工作仅仅是判断大圆是否被小圆完全覆盖。试探性离散化如果使用和例1相同的离散化策略，得到的时间复杂度为O(N3*k)，k为二分的次数，这个时间复杂度太