青烟绕指柔

计算几何

2-SAT(1) bfs(6) Codeforces(3) dfs(4) Hash(1) HDU(2) KM(1) LCA(2) Link_Cut_Tree(1) LIS(1) Splay(1) STL(7) WQS二分(1) 中等难度(6) 主席树(4) 二分(1) 分块(1) 前缀和(1) 动态规划(15) 博弈论(1) 双连通分量(1) 图论(158) 堆(3) 字符串(5) 差分(1) 并查集(13) 拓扑排序(4) 数位dp(3) 数学(1) 数论(12) 无旋treap(2) 最小环(2) 最小生成树(11) 最短路(18) 树形dp(1) 树状数组(16) 树结构(4) 树链剖分(1) 概率dp(2) 相对大小问题(1) 矩阵乘法(3) 离线算法(12) 线性基(2) 线段树(28) 背包问题(2) 莫队(1) 贪心(2) 距离表示(1) 题解(4)

/ 注册

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

计算几何--线段相交

swust oj 680 Jack Straws 1000(ms) 65535(kb) 450 / 1259 n the game of Jack Straws, a number of plastic or wooden “straws” are dumped on the table and ...

2019-12-27

0 429

poj 2069 最小球覆盖

Description During a voyage of the starship Hakodate-maru (see Problem 1406), researchers found strange synchronized movements of stars. Having heard...

2019-12-27

0 468

最小圆覆盖

题目描述给出N个点，让你画一个最小的包含所有点的圆。输入格式先给出点的个数N,2<=N<=100000，再给出坐标Xi,Yi.(-10000.0<=xi,yi<=10000.0) 输出格式输出圆的半径，及圆心的坐标，保留10位小数输入输出样例输入 #1复制...

2019-12-27

0 508

二维凸包

题目描述农夫约翰想要建造一个围栏用来围住他的奶牛，可是他资金匮乏。他建造的围栏必须包括他的奶牛喜欢吃草的所有地点。对于给出的这些地点的坐标，计算最短的能够围住这些点的围栏的长度。输入格式输入数据的第一行包括一个整数 N。N（0 <= N <= 10,000）表示农夫约翰想要围住的...

2019-12-27

0 435

旋转卡壳

例题：POJ 2187 旋转卡壳一般用来求平面中最远的两点的距离。我们很明显的可以发现，最远的两个点必然在凸包上，于是我们求出凸包之后，扫对踵点。利用凸包上的点依次与对应边产生的距离成单峰函数,面积上升到最高点后，又会下降。(具体证明可以从凸包定义入手用反证法解决) 然后就可以O(...

2019-12-27

0 479

多边形重心

例题：hdu 1115 给出一堆点，求多边形的重心。我们可以把多边形划分为许多三角形。三角形的重心很简单： x = ( x1 + x2 + x3 ) / 3 , y = ( y1 + y2 + y3 ) / 3 多边形的重心公式为：借用大佬博客的图片：https://blog.cs...

2019-12-27

0 610

自适应Simpson

Simpson是什么呢？就是如果我们要求一个积分，但是里面的f(x)十分麻烦，于是我们就需要用Simpson的抛物线来近似最后的答案。加一个自适应就是适应精度，当精度很小的时候，就直接返回。 Simpson公式：例题：Simpson例题 AC代码： #pragma GCC ...

2019-12-27

0 586

三角剖分与泰森多边形

泰森多边形：大概就是一个平面划分，平面上的每个点划分到离它最近的关键点上。 Delaunay三角剖分和泰森多边形是对偶图。 Delaunay三角剖分：定理：对于任何一种三角剖分，三角形个数和外围凸包点数之和为2n-2。 Delaunay三角剖分的性质 1.平面上的点集有且仅有唯一的Del...

2019-12-27

0 690