永远鲜红的幼月

计算几何学习

CF(19) dp(6) gcd的应用(1) sort(4) spfa(1) 二分(12) 几何(1) 博弈(2) 固定算法(1) 图论(11) 套题(5) 字符串匹配(1) 并查集(4) 思维(2) 搜索(4) 数学题(2) 数据结构(10) 数论(4) 未归档(192) 树状数组(1) 状压DP(1) 科普(3) 线段树(2) 网络流(3) 计算几何(4) 贪心(1) 题解(1)

/ 注册

全部文章 / 计算几何学习（共17篇）

凸包问题--旋转卡壳

前情提要： 1978年，M.I.Shamos在论文《Computational Ceometry》中介绍了一种寻找凸多边形直径的线性算法。 Shamos的算法就像绕着多边形旋转一对卡壳，因此便有了术语——旋转卡壳。旋转卡壳是一种高效的算法。被广泛运用在解决一些与凸包相关的问题。旋转卡壳充分利用了...

2019-03-13

0 1405

扫描线有关习题

总结一下关于扫描线的习题。正在更新中... Table of Contents HDU-1542-Atlantis，POJ-1151-Atlantis（扫描线+线段树） HDU-1255-覆盖的面积（扫描线+线段树，板子） HDU-1828-Picture||POJ-1177 Picture...

2019-03-12

0 824

洛谷-P3829-[SHOI2012]信用卡凸包（凸包，注意精度！！！！！！）

题目链接：https://www.luogu.org/problemnew/show/P3829 题目大意：中文题，易理解。思路：***！！精度卡了我一页的WA...（还是太菜了）经过简单的草图，如下图所示：随便举一个例子，然后发现，周长就是里面的小的多边形的周长+圆的周长。至于具体的证明，这...

2019-03-10

0 503

凸包问题--动态凸包（平衡树维护）

前景提要：继承上一张学习的凸包问题，下面我么来总结一下动态凸包的维护问题。一些点已经构成了一个凸包之后，新加入||删除一些新的点的时候，会对原有的凸包产生一些影响，如果每次都重新把所有点都重新计算一遍凸包的话，那将非常耗费时间，以至于必定会WA，因此，我们就学习动态凸包的维护方法。目录 ...

2019-03-06

0 942

POJ-1873-The Fortified Forest（二进制枚举+凸包）

题目链接：http://poj.org/problem?id=1873 题目大意：给出n棵树的位置（x，y）坐标，价值v和长度l。让你从中选择一些树，砍掉他们将其他的树围起来。要求砍的这些树的价值之和最小。按顺序输出砍的树。如果价值相同，输出砍的树最少的的方案。最后在输出一个：砍掉的这些树，围...

2019-03-02

0 600

凸包问题--Graham-Scan算法

凸包问题的两个算法，上一篇学习了简单好写的卷包裹法，现在我们学习Graham-Scan法。首先复习一下中学学过的极坐标。平面中取一定点A，从A点出发的一条射线AM，再选定一个长度单位和角度的正方向（通常取逆时针方向）。对于平面内任意一点B，都可以用有序对(，)(0<=<2)唯...

2019-03-02

0 927

凸包问题--卷包裹法

写在前面--- 现在我们学习凸包的有关算法（终于开始凸包的学习了）。也算是初步接触计算几何了。凸包的概念是在一个实数向量空间V中，对于给定集合X，所有包含X的凸集的交集S被称为X的凸包，表示为：在二维空间中，凸包也可以形象的理解为最小的包含所有点的凸多边形。 X的凸包可以用X=（x1...

2019-03-01

0 780

解析几何--最小圆覆盖

最小圆覆盖问题指平面上有n个点，给定n个点的坐标，找到一个半径最小的圆，将n个点全部包围，点可以在圆上。求最小圆覆盖问题的方法有很多种。一步一步学习。先介绍增量法的实现步骤。目录点增量法三角形增量法 HDU-3007-Buried memory（最小圆覆盖板子） BZOJ-1...

2019-02-28

0 2452

解析几何--与三角形有关的圆，多边形圆的扩展

三角形的外接圆三角形外接圆圆心是三条边上垂直平分线的交点。外接圆的半径是外心到顶点的距离。圆在解析几何中表示圆心坐标以及圆的半径。由：可知三角形面积与外接圆半径的关系。因此，可通过计算三角形面积得出外接圆半径。外心的坐标是两条边的垂直平分线交点的坐标。设三角形坐标为：A(x1...

2019-02-27

0 894

解析几何--对称，平移和旋转

对称问题就是计算几何中的经典问题，熟练掌握以及应用对称可以使得问题简化，时间复杂度也可能相对减少。平移和旋转时解析几何中常用的坐标变换方法。坐标变换可能出现在问题中，也可能出现在解题的过程中。解题时，通过巧妙的平移旋转，可以简化计算，使题目变得更加直观，方便解题。例如，对于对称图形，只需...

2019-02-27

0 1207