何事秋。

计算几何基本算法

AC自动机(4) bfs/dfs(5) bitset(3) CF刷题(23) dp一般看规律(11) dp基本算法(12) KMP(2) LCA(1) LCT(4) Prufer(2) SAM(3) STL(1) tarjan(1) 主席树/线段树(14) 二分/三分(2) 二分图(1) 位运算(1) 偏序问题(2) 分块(1) 分治/点分治/边分治(2) 单调栈(2) 单调队列(1) 博弈/sg(3) 博弈论基本算法(11) 后缀数组(1) 启发式合并(1) 哈希(4) 回文自动机(2) 图论一顿套模板(3) 图论基本算法(31) 基本算法(2) 多项式(1) 套题(1) 字典树(1) 字符串基本算法(27) 容斥(1) 平衡树/堆(2) 并查集(3) 序列自动机(1) 快速幂/矩阵快速幂(1) 思维只会A+B(5) 投稿(2) 拓扑序(1) 数位dp(1) 数学不好先打表(4) 数据结构基本算法(69) 数据结构瞎乱写(8) 数论分块(1) 数论只会gcd(20) 数论基本算法(64) 暴力(1) 最短路(3) 期望/概率(1) 期望dp/概率dp(1) 构造(3) 枚举(3) 树形dp(3) 树链剖分(5) 模拟只会猜题意(5) 生成树(1) 签到题(2) 线性dp(12) 线性基(2) 组合数学(1) 组合数学靠运气(2) 结论题(2) 网络流/费用流(5) 网络流基本算法(5) 群论(2) 背包dp(1) 莫比乌斯反演(1) 莫队(1) 虚树(1) 计数类dp(1) 计算几何(8) 贪心刚好过样例(3) 随机化算法(2)

/ 注册

全部文章 / 计算几何基本算法（共15篇）

二维几何——点类，常量设置：

这些代码未经过测试，存在安全隐患。。。。 const double eps=1e-8; const double dnf=1e20; const double pi=acos(-1.0); const int maxp=1010; //浮点型数值是否为0 int sgn(double x) {...

2020-09-04

0 526

二维几何——线类：

这些代码未经过题目测试，存在安全隐患。。。。 struct Line { Point s,e; Line(){} //两点 Line(const Point ss,const Point ee) { s=ss,e=ee; } ...

2020-09-04

0 373

二维几何——多边形类：

未经过题目测试。。。。 struct polygon { int n; Point p[maxp]; Line l[maxp]; void input(int nn) { n=nn; for(int i=0;i<n;i...

2020-09-04

0 444

二维几何——最小矩形面积覆盖，直线切凸多边形：

也未经过题目测试。。。。 //AB X AC double cross(Point A,Point B,Point C) { return (B-A)^(C-A); } //AB*AC double dot(Point A,Point B,Point C) { return (B...

2020-09-04

0 558

二维几何——半平面类：

主要计算半平面交 //半平面交 struct halfplane:public Line { double angle; halfplane(){} //表示向量 s->e 逆时针 (左侧) 的半平面 halfplane(Point ss,Point ee) ...

2020-09-04

0 387

二维几何——多圆类：

主要计算面积并、面积交，覆盖多次面积： const int maxn=1010; struct circles { circle c[maxn]; double ans[maxn];//ans[i] 表示被覆盖了i次的面积 double pre[maxn]; in...

2020-09-04

0 517

二维几何——平面最近点对：

存个模板：是用分治写的时间复杂度 nlogn 但是本题好像还有一种玄学做题法：我们充分发扬人类智慧：将所有点全部绕原点旋转同一个角度，然后按x坐标排序根据数学直觉，在随机旋转后，答案中的两个点在数组中肯定不会离得太远所以我们只取每个点向后的5个点来计算答案这样速度快得飞起，在n...

2020-09-04

0 831

二维几何——平面最远点对：

求个凸包，然后在凸包上求：时间复杂度大概是 O（nlogn+n）： #include<iostream> #include<cstdlib> #include<cstdio> #include<algorithm> #include<cstr...

2020-09-04

0 517

三维几何——点类、线类、平面类：

未经过题目测试。。。 #include<iostream> #include<cstdlib> #include<cstdio> #include<algorithm> #include<cstring> #include<stri...

2020-09-04

0 452

三维几何——三维凸包：

时间复杂度和空间复杂度都是O（n*n）级别的。 #include<iostream> #include<cstdlib> #include<cstdio> #include<algorithm> #include<cstring> #in...

2020-09-04

0 417