NULL
博文链接：https://yye.iteye.com/blog/740390
2021-06-26 14:45:42
3.57MB
1
㈠ 点的基本运算
1. 平面上两点之间距离
2. 判断两点是否重合
3. 矢量叉乘
4. 矢量点乘
5. 判断点是否在线段上
6. 求一点饶某点旋转后的坐标
7. 求矢量夹角
㈡ 线段及直线的基本运算
1. 点与线段的关系
2. 求点到线段所在直线垂线的垂足
3. 点到线段的最近点
4. 点到线段所在直线的距离
5. 点到折线集的最近距离
6. 判断圆是否在多边形内
7. 求矢量夹角余弦
8. 求线段之间的夹角
9. 判断线段是否相交
10.判断线段是否相交但不交在端点处
11.求线段所在直线的方程
12.求直线的斜率
13.求直线的倾斜角
14.求点关于某直线的对称点
15.判断两条直线是否相交及求直线交点
16.判断线段是否相交，如果相交返回交点
㈢ 多边形常用算法模块
1. 判断多边形是否简单多边形
2. 检查多边形顶点的凸凹性
3. 判断多边形是否凸多边形
4. 求多边形面积
5. 判断多边形顶点的排列方向，方法一
6. 判断多边形顶点的排列方向，方法二
7. 射线法判断点是否在多边形内
8. 判断点是否在凸多边形内
9. 寻找点集的graham算法
10.寻找点集凸包的卷包裹法
11.判断线段是否在多边形内
12.求简单多边形的重心
13.求凸多边形的重心
14.求肯定在给定多边形内的一个点
15.求从多边形外一点出发到该多边形的切线
16.判断多边形的核是否存在
㈣ 圆的基本运算
1 .点是否在圆内
2 .求不共线的三点所确定的圆
㈤ 矩形的基本运算
1.已知矩形三点坐标，求第4点坐标
㈥ 常用算法的描述
㈦ 补充
1．两圆关系
2．判断圆是否在矩形内
3．点到平面的距离
4．点是否在直线同侧
5．镜面反射线
6．矩形包含
7．两圆交点
8．两圆公共面积
9. 圆和直线关系
10. 内切圆
11. 求切点
12. 线段的左右旋
13．公式
2021-06-22 10:19:24
13KB
1
ACM Fighting! 2
1.计算几何 5
1.1 注意 5
1.2几何公式 6
1.3 多边形 8
1.4多边形切割 11
1.5 浮点函数 12
1.6 面积 18
1.7球面 18
1.8三角形 19
1.9三维几何 22
1.10 凸包 30
1.11 网格 32
1.12 圆 33
1.13 矢量运算求几何模板 35
1.14结构体表示几何图形 47
1.15四城部分几何模板 52
1.16 一些代码 54
1.16.1 最小圆覆盖_zju1450 54
1.16.2 直线旋转_两凸包的最短距离(poj3608) 58
1.16.3 扇形的重心 62
1.16.4 根据经度纬度求球面距离 62
1.16.5 多边形的重心 64
1.16.6 存不存在一个平面把两堆点分开(poj3643) 66
1.16.7 pku_3335_判断多边形的核是否存在 67
1.16.8 pku_2600_二分+圆的参数方程 74
1.16.9 pku_1151_矩形相交的面积 76
1.16.10 pku_1118_共线最多的点的个数 78
1.16.11 pku2826_线段围成的区域可储水量 80
1.16.12 Pick公式 84
1.16.13 N点中三个点组成三角形面积最大 86
1.16.14 直线关于圆的反射 89
1.16.15 pku2002_3432_N个点最多组成多少个正方形(hao) 94
1.16.16 pku1981_单位圆覆盖最多点(poj1981)CircleandPoints 97
1.16.17 pku3668_GameofLine_N个点最多确定多少互不平行的直线(poj3668) 99
1.16.18 求凸多边形直径 100
2.组合 102
2.1 组合公式 102
2.2 排列组合生成 102
2.3 生成gray码 104
2.4 置换(polya) 104
2.5 字典序全排列 105
2.6 字典序组合 105
2.7 一些原理及其例子 106
3.数论 108
3.1 阶乘最后非0位 108
3.2 模线性方程组 108
3.3 素数 110
3.4 欧拉函数 114
3.6高精度 116
3.6.1平方根 116
3.6.2 高精度乘幂 117
3.7 高斯消元回代法 122
3.8 数值计算 124
3.8.1 定积分计算 124
3.8.2 多项式求根(牛顿法) 125
3.8.3 周期性方程(追赶法) 127
4.排序 128
4.1快速选择算法 128
4.2归并排序+逆序数的求取 128
5.字符串 130
5.1 KMP应用 130
5.2 后缀数组 131
5.3 中缀表达式转后缀表达式 134
5.4 Firefighters 表达式求值 135
6.博弈 139
6.1 博弈的AB剪枝 139
6.1.1 取石子 139
6.2 博弈 SG函数 局势分割 141
7.数据结构 142
7.1 TRIE 142
7.2 线段树 147
7.3 并查集 151
7.4 树状数组 152
7.5 点树 154
7.6 STL 156
7.7 离散化 157
8.图论 158
8.0 2-SAT 158
8.2 寻找Euler回路 163
8.3 拓扑排序 163
8.4 差分约束系统 164
8.5 笛卡尔树 165
8.6 LCA和RMQ 167
8.7 割和桥 171
8.8 最小生成树(kruskal) 172
8.9 最短路径 173
8.10 最大网络流 175
8.11 最小费用流 180
8.12 最大团问题 182
8.13 二分图匹配 184
8.14 带权的最优二分图匹配 184
9.搜索算法概略 187
9.1 迭代深搜+IDA* 187
9.2 分之界限法（深搜） 189
9.3 A* 8数码问题( pascal ) 192
9.4 优先队列广搜 194
10.应用 197
10.1 Joseph问题 197
10.2 N皇后构造解 197
10.3 布尔母函数 198
10.4 第k元素 199
10.5 幻方构造 199
10.6 模式匹配(kmp) 201
10.7 逆序对数 201
10.8 字符串最小表示 202
10.9 最长公共单调子序列 202
10.10 最长子序列 204
10.11 最大子串匹配 204
10.12 最大子段和 205
10.13 最大子阵和 206
11.其它 207
11.1 大数(只能处理正数) 207
11.2 分数 212
11.3 矩阵 214
11.4 线性方程组 216
11. 5 线性相关 218
11.6 日期 219
11.7 读入 220
11.8 函数 220
2021-05-23 16:29:08
75KB
1