Daowuu

计算几何

动态规划(1) 博弈论(1) 图论(9) 字符串(5) 数学(10) 数据结构(3) 未归档(1) 题解(2) 高精度(1)

/ 注册

全部文章 / 计算几何（共8篇）

最小圆覆盖来自专栏

给定n个点，求一个最小的圆包围所有的点。随机增量法时间复杂度 O(n) #include<bits/stdc++.h> using namespace std; const int maxn = 1e6+1; const double eps = 1e-8; int sgn(do...

计算几何

2020-10-15

0 772

旋转卡壳来自专栏

计算几何

2020-10-14

0 680

最近点对来自专栏

给定平面上n个点，找出其中的一对点的距离，使得在这n个点的所有点对中，该距离为所有点对中最小的考虑以下分治算法：设平面上的点都在点集S中，为了将S线性分割为大小大致相等的2个子集S1和S2，我们选取一垂直线l（方程：x=m）来作为分割直线。其中m为S中各点x坐标的中位数。由此将S分割为S1={p...

计算几何

2020-10-14

0 1010

半平面交来自专栏

计算几何

2020-10-13

0 583

计算几何基础来自专栏

控制精度 // 控制精度 const double Pi = acos(-1.0); // 高精度圆周率 const double eps = 1e-8; // 偏差值，有时用 1e-10 int sgn(double x) { // 判断...

计算几何

2020-09-26

0 848

解析几何来自专栏

点的坐标直线的交点图中有四个顶点 A、B、C、D，组成两条直线 AB 和 CD，交点是 P。以下两个关系成立：联系上面两个方程，得到交点 P 的坐标如下：注意：在 Cross_point() 中要对（s2-s1）做除法，所以在调用 Cross_point() 之前应该保证，即直线 AB、CD...

计算几何

2020-09-26

0 758

自适应辛普森法来自专栏

二次函数的定积分对于一个二次函数，显然有对于一个奇怪的函数，为了对其求导，我们可以用一个图像近似且容易求导的函数（这里我们使用二次函数）来代替它(拟合)，这样的话精度误差可能会很大，因此我们需要将函数分段拟合。自适应辛普森法显然我们并不知道分成多少段合适，因为段分得越多，精度误差越小，...

计算几何

2020-09-22

0 771

凸包来自专栏

凸包问题给定义一些点，求能把所有这些点包含在内的面积最小的多边形，可以想象有一个很大橡皮箍，它把所有的点都箍在里面，在橡皮箍收紧之后，绕着最外围的点形成的多边形就是凸包。如下图： Graham扫描法时间复杂度：O(n㏒n)思路：Graham扫描的思想和Jarris步进法类似，也是先找到凸包上的...

计算几何凸包

2020-07-06

0 790