分类
标签
2-SAT AC自动机 BFS CDQ dfs DP fail树 FFT FFT&NTT FWT hash KD-Tree KMP LCA SPFA STL Tarjan Treap Trie 主席树 乱搞 二分 二分图匹配 二分答案 二维SPFA 交互 位运算 其他 最小生成树 分块 区间DP 半平面交 博弈论 可持久化 可持久化Trie树 后缀数组 图库 平衡树 并查集 插头DP 数学 数论 无旋Treap 日记 暴力 权值树状数组 栈 树DP 树套树 树状数组 树贪心 概率DP 模拟 欧拉定理 点分治 状压DP 生成函数 矩阵乘 线性规划 线段树 组合 网络流 群论 莫比乌斯反演 计算几何 贪心 费用流 高斯消元
519 字
3 分钟
计算几何初步
1.什么是计算几何
维基百科计算几何
计算几何是一门兴起于二十世纪七十年代末的计算机科学的一个分支,主要研究解决几何问题的算法。
简单来说就是用计算机算解析几何
2.计算几何的恶心之处
有精度误差1
需要讨论各种边界情况
代码长(看一看NOI2017D2T3的标称就知道了)
解决精度问题
设为非常小的量
3.二维矢量
矢量
- 既有大小又有方向的量
- 又称为向量
矢量的表示
- 在n维空间下,矢量经常被表示为
- 在二维空间中则以来表述
点积
矢量的模
矢量的长度
! 二维叉积
二维叉积满足逆交换律:
有向面积
- 由和所成的平行四边形的面积为 的值
- 去掉绝对值二维叉积定义为有向面积
有向面积的符号
伸出右手将四指由沿小于平角转到若拇指指向纸面上方则为正否则为负
二维矢量的旋转
将矢量逆时针旋转后为
二维矢量的极角
极角指示矢量的方向,以x轴正半轴逆时针转过的角度来指示 矢量的极角为
直线
用两个相异点来表示 表示直线上任意一点
点到直线的距离
点到直线的距离 即
分点
若A,B,C共线,且 则
三角形的面积
两直线交点
为完待续…(2017-8-6)
Footnotes
在计算几何问题时很多时候用到复杂的浮点运算和三角函数运算,这样就会产生精度问题 ↩