茂名网站建设,下载app,重庆百度seo排名,用ps做网站还是wd2107 Quoit Design 典型最近点对问题POJ 3714 Raid 变种最近点对问题B#xff0c;最小包围圆最小包围圆的算法是一种增量算法#xff0c;期望是O(n)。ZOJ 1450 Minimal CircleHDU 3007 Buried memoryC#xff0c;旋转卡壳POJ 3608 Bridge Acr…2107 Quoit Design 典型最近点对问题POJ 3714 Raid 变种最近点对问题B最小包围圆最小包围圆的算法是一种增量算法期望是O(n)。ZOJ 1450 Minimal CircleHDU 3007 Buried memoryC旋转卡壳POJ 3608 Bridge Across Islands 旋转卡壳解两凸包最小距离POJ 2079 Triangle 旋转卡壳计算平面点集最大三角形1.2 比较简单的题目HDU 3264 Open-air shopping malls 圆面积相交问题如果用二分法做的话不难CII 3000 Tree-Lined Streets几何贪心CII 4676 Geometry Problem模板题HDU 3272 Mission Impossible枚举镜面反射思想POJ 3334 Connected Gheeves二分答案面积判定POJ 1819 Disks模拟一下CII 3905 Meteor貌似还是比较简单ZOJ 2589 Circles平面图的欧拉定理圆的相交POJ 2194 Stacking Cylinders向量旋转二。经典算法2.1 三角剖分三角剖分这个东西貌似去年流行了一下高校联赛时某U连续出了两次。实际上对多边形进行三角剖分是一个很常见的算法思想因为三角形是一个比较简单的凸多边形可以对两个三角形比较容易地求公共面积这也是三角剖分最常见的用途。对这个算法进行扩展就可以求两个简单多边形的面积交了。主要是理解有向面积的概念。第一类是圆与三角形的相交主要做法是分情况讨论。POJ 3675 Telescope 三角形剖分圆与三角形的交POJ 2986 A Triangle and a Circle 三角形剖分圆与三角形的交ZOJ 2675 Little Mammoth 三角形剖分圆与三角形的交第二类是多边形与多边形相交。HDU 3060 Area2 简单多边形面积并三角剖分三角形剖分的另一种变种是梯形剖分应用起来稍有局限性但是比三角形剖分好写。POJ 3148 ASCII Art 多边形梯形剖分半平面交多边形的重心问题也是三角形剖分的应用CII 4426 Blast the Enemy!2.2 极角排序顾名思义极角排序一般就是有一个圆心的问题将平面上各个点按照与圆心极角进行排序。然后就可以在线性扫描之中解决一些统计问题。不过这类问题就稍稍超出计算几何范畴了。UVA 11696 Beacons 颇为经典的极角排序的统计问题记得darkgt大牛有一篇文章提到这个题目。CII 4064 Magnetic Train Tracks极角排序的统计问题补集思想。UVA 11704 Caper pizzaPOJ 2280 Amphiphilic Carbon Molecules极角排序相当巧妙地解决了这个问题。2.3 扫描线算法扫描线算法需要使用到平衡树辅助写起来比较复杂(对于本菜而言)。关于平衡树我建议是直接使用STL的set或map。所以你需要掌握一些C的知识才能够看懂一份使用了map与set的代码。当年学习OI牛的代码我看得很纠结。不过只要理解了“事件点”这一个概念后就比较好办了。HDU 3124 Moonmist 二分扫描线。最近圆对不存在改编最近点对的方法。不过当时数据弱很多人乱搞过了POJ 2927 Coneology 平衡树扫描线与上题类似。下面两个题目都是关于多边形的扫描线算法关于平面上许多凸多边形套了多少层的问题。CII 4125 Painter 这个是Final题比较简单是判断三角形嵌套层数的。UVA 11759 IBM Fencing上题是三角形这题是多边形稍稍难了一点。不过理解好扫描线算法的话应该没有问题。2.4 其他题目POJ 3528 Ultimate Weapon模板化的三维凸包。知道几个三维有向体积的概念即可比较容易理解三维凸包的算法。三维凸包算法又是一种增量算法。三。不确定算法/极值问题POJ 3301 Texas Trip 算是一种模拟退火求极值的问题通过平面旋转找到最佳答案。SPOJ 4409 Circle vs Triangle(AREA1)也是模拟退火UVA 11562 Hard Evidence应用三分极值法求极值。四。传统几何、公式题UVA有一个名叫Shahriar Manzoor喜欢出这些题目喜欢这类题目的同志可以研究一本名叫《近代欧式几何学》的书。不过这些题目一般中学几何知识能够解决。CII 4413 Triangle Hazard梅涅劳斯定理想不到SCNU校赛出到了UVA 11524 InCricle三角形内切圆性质联立海伦公式CII 4714 In-circles Again还是公式推导POJ 2208 Pyramids欧拉四面体公式五。几何结合其他算法麻烦题转自:http://www.cppblog.com/zzfmars/articles/121794.htmlHDU 2297 Run百度杯的题目利用到了zzy的半平面交的极角排序思想。CII 4448 Conduit Packing问一个大圆能否放下四个小圆。颇为变态的Final题算法都很基础就是二分一个答案枚举两个已知圆求与已知的两圆公切的第三个圆枚举放置的位置……关键是不好想。CII 4510 Slalom 几何最短路UVA 11422 Escaping from Fractal Bacterium 麻烦题主要还是向量旋转。HDU 3228 Island Explorer利用了最小生成树的性质。CII 4499 Camera in the Museum有关圆形处理的很不错的题目。CII 2395 Jacquard CircuitsPick公式的应用POJ 3747 Scout YYF II又是一个几何问题需要猜想一下。POJ 3336 ACM Underground几何预处理并查集CII 4428 Solar Eclipse也是不错的题目涉及圆的问题CII 4206 Magic Ringsdancing links解重复覆盖问题二分百度杯也有个类似的题目。POJ 1263 Reflections与下面一个题目都是一类光线在球面上反射问题。解决方法是解析几何参数方程向量旋转等等。CII 4161 Spherical Mirrors上面题目的三维版本。POJ 3521 Geometric Map复杂的预处理可以用于自虐CII 3270 Simplified GSM Network 虽然有着V图的模型但是规模小所以无须出动V图算法用半平面交即可。变态级的V图算法可以咨询三鲜教主。CII 4617 Simple Polygon平面上有一堆点叫你用一笔画把这些点连起来连成一个闭合的简单多边形线不允许出现相交。改造一下凸包算法即可。当然除了上述的题目外还有许多比较精彩的计算几何题目等待大家发掘
