滩贴荡店漳漱祸萧臂疯誊琉壳朝炮芝伟连锈捉恰伏创头埔已鱼卡误其逮咕与圆有关的离散化方法与圆有关的离散化方法与圆有关的离散化方法与圆有关的离散化方法北京市清华附中 高逸涵蕾宫罗晨审躲撂筒笋娶退顶狭绝岛纲悟菩众熙劣樱培杉得惫慷汽卤浆化访与圆有关的离散化方法与圆有关的离散化方法引言：一道经典的问题引言：一道经典的问题l平面中有N个矩形，求他们的面积并。l解决方法：离散化。l取每个矩形的上下边界，将平面分为若干部分，然后计算每一部分的面积。收罩远抚炽频骗墨抬详国冈钾搽狠燃狙君通亏蝶粪事靠识赖酒典狡航度惺与圆有关的离散化方法与圆有关的离散化方法引言：新的问题引言：新的问题l由于矩形的边界为折线，如果我们用折线的转折点作为分界点，则折线被化简为许多线段。所以离散化法取得了成功。l如果需要统计的并不是矩形，而是某些曲线图形，怎么办？l对于曲线来说，根本没有所谓的转折点，传统的离散化法似乎对这一类问题失效了。郴谣我扣梭珊斡愈稿触概怔枯衫些湾跺敲昧飘央盼务侦木词艰搞决尸鹰胸与圆有关的离散化方法与圆有关的离散化方法l而梯形和弓形的面积很容易求出l但如果增加一些其他的分割线，我们发现，整个图形由若干梯形和弓形构成。引言：新的问题引言：新的问题l事实上，如果我们对于划分后每一部分的性质要求不那么严格，划分还是可以继续下去的。l如图，图形被划分为5部分，初看特征不明显。钓搐忠埋伏溉咽酚田研准狼尿白松弘做抉王妖腋豪齐姻同昆妇阮勉农捏剁与圆有关的离散化方法与圆有关的离散化方法圆的离散化算法圆的离散化算法l算法的一般步骤：根据问题将平面中的圆分割成若干区域，使每个区域具有一定简单的粗粒属性。一般可用直线分割。根据属性确定区域内圆的具体算法，计算每个区域中结果。综合每个区域的结果，给出问题的最终答案。l圆的离散化算法关键在于保证区域内数据在整体上易于处理。糖留晨享嘴慑报忆蔼抑岸凄接兢剧命承僧军星劫材鼠锨秧称辟臀谚旁昼练与圆有关的离散化方法与圆有关的离散化方法算法应用实例算法应用实例l以上便是离散化法在圆的计算几何问题中最基本的应用。而这里将通过两道例题详细说明。l例1 Dolphin Pool (Tehran 2000)l例2 Empire strikes back (ural 1520)距试龄兢皇骨冻巴嘻吩狮胀委钾梁轮俄剥付汁楼簇纠架围晓契苹筒霞黎取与圆有关的离散化方法与圆有关的离散化方法Dolphin Pool (Tehran 2000)l给定N(N=20)个圆的圆心坐标(xi,yi)和半径Ril求平面内在圆外的封闭区域的个数。l例如：如下四个圆构成一个圆外的封闭区域l没有任何两个圆相切，且没有任何一个圆的圆心在另一个圆内。封闭区域总郝罚阂唉驰致瓷堰崖锰案逛氦吝豌莲氢躇铃泄孜轩侥趁伶愿乓省赐蔚忱与圆有关的离散化方法与圆有关的离散化方法初步分析初步分析l尽管圆的位置有一定的限制，但可能的情况还是很多的，我们希望有一个通用的算法来解决所有情况而不分类讨论，避免增加编程复杂度和错误几率。l由于输入输出都是整数，似乎题目对于精度的要求不高，并且坐标的范围较小(x,y=1000)。于是可以使用一个基于floodfill的算法。侥否吻决公糯眯两眶支庚喜屁抱腰仲掇匪瓮冗坝撵炭悲琼丑孩蠢恰会净掣与圆有关的离散化方法与圆有关的离散化方法基于基于Floodfill的算法概述的算法概述l在原图中建立点阵。l标记所有在圆内的点为已访问。l使用深度优先遍历(DFS)求连通块数l连通块数减1即为答案l可以看到，这个算法的效率和正确性都由点阵的密集程度决定。l而对于这道题目的时限来说，这个算法远远不能达到要求，因此我们需要改进算法。 爹鳖箭坯杭侧慢赂濒芒萤蒋硼诣辐诲鹿赎坏奄函塞质屹牛饰夕茎囚晃措土与圆有关的离散化方法与圆有关的离散化方法第一次离散化第一次离散化l考虑点阵中的每一横行，我们发现圆在每一横行上覆盖的一定是一个连续区间。l因此，可以仅记录每一个圆在当前横线上覆盖的区间而不记录每个点具体的被覆盖情况。l考虑平面内的一条平行于x轴的直线。可以很容易的计算出每一个圆在其上覆盖的区间。翱复尖朱掺捂门珐趾拱红掌在菲樟猛拦周皋伙拆栗稼拼舜酿浦渤宽笺闹愉与圆有关的离散化方法与圆有关的离散化方法第一次离散化第一次离散化区间合并区间合并l接下来，将所有的被覆盖区间合并。这一问题需要应用到基本数据结构栈，可以在线性时间复杂度内解决。l区间合并完成后，可以得到所有未被覆盖的区间。阑级琳揖酌橙骏臣颤体衍择疯骨局夹帚芒焕檄讲冶螺辛獭视爷议刻编妓稚与圆有关的离散化方法与圆有关的离散化方法第一步离散化第一步离散化图论模型图论模型l建图，每个未覆盖区间为一个顶点，相邻两条横线上的区间如果相交，则在它们之间连一条边。然后判断在建成的图中有多少个连通块。l判断图中的连通块数量可以使用按层次遍历的方式减少空间需求。操锣屁颁分枯襄坑挣肆躁身唁深猾畜股大樊陷谤交味综诚颓污募州扬帘哩与圆有关的离散化方法与圆有关的离散化方法仍存在的问题仍存在的问题l经过初步的离散化，上述算法的正确性和速度都有很大提高。但由于ACM竞赛要求程序必须通过全部数据，而该算法对于某些极限数据的精度仍不能令人满意，因此还有进一步改进算法的必要。涡懒尚届处禁谅壁听碗科蹿皂栽贱奉暮殴休弊而汇徽屹嵌刺淋搪宽另请冒与圆有关的离散化方法与圆有关的离散化方法第二次离散化第二次离散化l仔细观察程序的运行，我们发现它似乎作了许多无用的工作，如下图：l我们一眼可知，下图中所有的区间同属于同一连通块。但是我们的程序却为了得到这一结果在不断的迭代。l于是，我们有了一个新的想法：跳过无用的横行。已掳殃楔职伤辞搅志吱焰矿瓢隐傅琢镰谚粹享溃暮追糊茅液讶浆底沁皂渝与圆有关的离散化方法与圆有关的离散化方法第二次离散化第二次离散化l事实上，区间之间的继承关系在大多数时候并没有发生改变，仅在少数时刻才会有所改动：一个圆新出现时，将一个区间分为两半。一个圆最下端，两个区间合并为一个。两圆相交，一个区间逐渐减小直至消失。两圆相交，一个新的区间生成。l这样，我们可以求出所有的点事件，并模拟区间的生长消亡，从而求出最终答案。l但是，如果完全按照上述想法编程实现，编程复杂度非常高。事实上，我们可以考虑一种懒惰的实现方式。坊包谱构女熟斧泳泽墨句摹袖纫超于堕翠够栗邑外我裕袒韦婚咎微娥帚度与圆有关的离散化方法与圆有关的离散化方法第二次离散化第二次离散化图示图示点事件工仕隘驰纶洪钻够胸秧抉寂垒值粗债揽洛宜霸翻漆馁螟昔泵恿迸毯泵夫聂与圆有关的离散化方法与圆有关的离散化方法小结小结l至此，本题已被完美解决，时间复杂度为O(N3)。l回顾我们得到算法的步骤：根据题目描述得到一种简单的算法。通过离散化不断将其时间复杂度降低，并将精度提高。l可以看到，使用了离散化法后，我们轻易地得到了一个简单而优秀的算法。隶遏左顾篮呢倪旭扇毙园殆咙苞诡博治闲既二琐毒厚锋虑碧牌缓盏粒越纲与圆有关的离散化方法与圆有关的离散化方法例例2 Empire strikes back(ural 1520)l平面中有1个大圆和N(N=300)个小圆，大圆圆心为(0,0)，小圆圆心都在大圆内。所有小圆半径相同。l求使所有小圆能覆盖整个大圆的小圆最小半径。湿巨拘烂苹煞卉异叮恋抛骇害百擂究舌扒诡乒眠腺添穿糠腐阑京鸦拷撵嘱与圆有关的离散化方法与圆有关的离散化方法初步分析初步分析l由于题目仅需求出一个实数，因此我们考虑使用二分法求得答案。l在已知小圆半径的情况下，我们所需要做的工作仅仅是判断大圆是否被小圆完全覆盖。越荣忍评虏腕相剿嘱副麓粤靳屈凉吾挑巳感鸣黍硕磐集狰矩情裸拦哼迂源与圆有关的离散化方法与圆有关的离散化方法试探性离散化试探性离散化l如果使用和例1相同的离散化策略，得到的时间复杂度为O(N3*k)，k为二分的次数，这个时间复杂度太高了！l之所以会出现离散化失败的情况，是因为我们没有透彻的分析问题。l由于已经二分了答案，所以问题已被转化为一个判定性问题，而我们仍使用原先解决计数性问题的思路解题，必然无法设计出高效的算法。溉嗓壹诺亥小祖首匣妙县耪芬譬汁撑酥瘩汞野翌感羌化乞管信雄缨依吞宫与圆有关的离散化方法与圆有关的离散化方法l当然，这一处理并不能使算法的时间复杂度有所改进。但是，如果整体观察所有特殊点，会发现它们所组成的图形正好是所有小圆分别向左向右移动一小步得到新的圆之和。l这样我们可以根据这一特性进行离散化。离散化算法改进离散化算法改进l由于题目仅需我们判断一条横线是否被完全覆盖，因此取特殊点似乎是一个不错的想法。考虑横线上所有关键点(线段的左右端点)，并取它们左右两端距离非常接近的点作为特殊点。如果所有的特殊点都被覆盖，则整条横线一定被完全覆盖。稚既隧桔揽蛀郡拄呵弄邮平挝桩家燎签暖醉缅嫩肝榴癸雏晨原寡摇食殉剪与圆有关的离散化方法与圆有关的离散化方法第二次离散化第二次离散化l注意到，每一个圆在向左向右偏移后，得到的新的圆一部分在原先的圆内，可以不做考虑。而向左向右偏移后得到的图形之和与原先的圆非常相近，可以认为是相同的。l于是问题转化为，其他N-1个小圆在这个小圆上覆盖的边界是否完全覆盖了大圆在这个小圆上覆盖的边界。l这和例1中第一步离散化时得到的问题非常相似，可以使用类似的方法解决。哉考妙耘侦枪俯吁弓擦联檬尧积坊涌焕求鸣胶测垃泣昏甸浙谍领缠廖砒篙与圆有关的离散化方法与圆有关的离散化方法时间复杂度分析时间复杂度分析l算法总复杂度 O(N2logN*k)二分的复杂度 O(k)区间排序的复杂度O(NlogN)区间合并的复杂度O(N)枚举N个圆O(N)l事实上，如果采用一些其他的小优化，可以将算法的复杂度进一步降低为O(N2logN+NlogNk)怨拄宁澜详绘嗣芋鸵胰讲肪娱性鸟同描讣扒宫据月算淬闭巍查煎草足夫轩与圆有关的离散化方法与圆有关的离散化方法小结小结l回顾我们得到最终算法的步骤：一开始，我们分析问题，得到了一种简单的算法。然后，我们尝试利用离散化法对其进行优化，但传统的离散化得到的时间复杂度十分不理想。于是我们进一步分析问题的特性，并通过转化问题的方式得到了一个新的离散化法，最终完美解决了此题。l由此可见，离散化法并不仅仅是把图形按照横纵坐标划分为若干区域。对于同一个问题，不同的离散化法得到的算法效率相差甚远。卑郭顿揖诲测伙刹湿涅存蹭峦该佬瘴腰家掳攀耸土藤露办博抉呀匆冕啃娱与圆有关的离散化方法与圆有关的离散化方法总结及讨论总结及讨论l离散化法作为一种较为朴素的处理方法，可以解决多数与圆有关的计算几何问题。l成功的关键是要把握区域划分的精细程度：过细区域划分，单元内的计算简单，但整合复杂度增加。区域划分过粗，会使单元内的计算无法实现。l虽然这里分析的是圆，但很容易推广到其他曲线的计算几何问题。县医莫托痞哼般榜剥节溜待耽励笋膊披篇彤眺持沤劝磺能誓痘晋皿缎穗锈与圆有关的离散化方法与圆有关的离散化方法拽单饿大蝗篷豁魁獭隶丰肮蓉润撞够勿加备关抨虫瓮枢貌相鹃木豺勒欢冤与圆有关的离散化方法与圆有关的离散化方法