何事秋。
何事秋。
全部文章
计算几何基本算法
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
443
二维几何——最小矩形面积覆盖,直线切凸多边形:
也未经过题目测试。。。。 //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
557
二维几何——半平面类:
主要计算半平面交 //半平面交 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
416
首页
上一页
1
2
下一页
末页