目录
二维计算几何基础
点、向量、直线
点:\((x,y)\) .
向量:\((x,y)\) .
向量的运算(\(A=(a_1,a_2),\ B=(b_1,b_2)\)):
-
加减:\(A\pm B=(a_1\pm b_1,a_2\pm b_2)\)
-
数乘:\(k\cdot A=(k\cdot a_1,k\cdot a_2)\)
-
模长:\(|A|=\sqrt{a_1^2+a_2^2}\) .
-
幅角:\(\theta=\arctan\frac{a_2}{a_1}\)(可以用
atan2
求).因为是 \(\tan\theta=\frac{a_2}{a_1}\),所以一般情况极角排序(按幅角排序)可以用斜率排 .
-
点积:\(A\cdot B=a_1b_1+a_2b_2=|A|\cdot |B|\cdot\cos\theta\) .
判断夹角:\(A\cdot B>0\) 锐角,\(A\cdot B=0\) 直角,\(A\cdot B<0\) 钝角 .
-
叉积:\(A\times B=a_1b_2-b_1a_2=|A|\cdot |B|\cdot\sin\theta\)(有向面积).
可以看成行列式:\(A\times B=\begin{vmatrix}a_1&a_2\\b_1&b_2\end{vmatrix}\) .
判断方向:\(A\cdot B>0\) 逆时针,\(A\cdot B=0\) 共线,\(A\cdot B<0\) 顺时针 .
-
旋转:\((a_1,a_2)\) 转 \(\theta\):\((a_1\cos\theta-a_2\sin\theta,a_1\sin\theta+a_2\cos\theta)\) .
直线:记两个点 \(A,B\),那么如果向量 \(\bm v=B-A\),直线上的点就可以表为 \(A+\bm vt\),限制 \(t\) 可以得到线段或射线 .
点到直线的距离:
- 文化课知识:\(P(x_0,y_0),\ \ell:ax+by+c=0\),距离:\[\operatorname{dist}(P,\ell)=\dfrac{|ax_0+by_0+c|}{\sqrt{a^2+b^2}} \]
- 叉积算出平行四边形面积然后除以底 .
线段相交:
- 跨立实验:两端点在另一条直线的两侧(叉积判断).
- 需要特殊处理共线情况 .
求交点:解方程 .
特殊情况(三点共线、四点共圆)在某些情形下可以直接扰动解决 .
POJ 3304 Segments
给 \(n\) 条线段,问有没有一条直线,满足这些线段在直线上的投影有公共点 .
\(n\le 100\) .
Solution
考虑找一条过所有线段的直线然后画一条与其垂直的线就好了 .
只需要连每两个线段端点然后判断即可找到一条过所有线段的直线 .
需要特判 \(n=1\) .
时间复杂度 \(O(n^3)\) .
POJ 2826 An Easy Problem?!
给两块长度相等的板子,天上垂直落下雨滴,问最后接到多少水 .
Solution
就是找到线段最高点连一下算三角形面积,有一个重要边界情况需要特殊处理:
多边形基础
多边形:用顶点表示 .
简单多边形面积:三角剖分,答案等于相邻边叉积和的一半 .
简单多边形重心:三角剖分,三角形是平凡的,然后合并就行了 .
点和多边形的位置关系(PIP):从点出发引一条射线,判断交点奇偶性,可能需要多引几条规避边界问题 .
凸包
凸包就是最小的包含所有给定点的凸多边形 .
\([0,n]^2\) 上整点凸包点数上界:\(O(n^{2/3})\),证明细节可参考杨景钦 2017 年集训队论文 .
Andrew 算法
单调栈处理即可 .
详细说明 .
动态凸包
动态凸包:带插入删除维护凸包信息 .
每次插入只会改 \(O(1)\) 个点,删除必须先插入,所以维护凸包的结构复杂度均摊下来是没有问题的 . 只需要用平衡树状物维护上下凸壳就可以了 .
练习题(板子):
半平面交
半平面:一条直线一侧的位置 .
凸包和半平面交是对偶问题,所以做法也是基本相似的 . S&I 算法:极角排序后单调栈维护 .
HNOI2012 射箭
有若 \(n\) 条竖着的线段 \(x=x_0,\ y\in[y_1,y_2]\) 组成序列 \(\{a\}\),画一个过原点的抛物线问过的线段和线段序列 \(\{a\}\) 的 LCP 最长是多少 .
\(n\le 10^5\) .
Solution
起手二分,那么一条抛物线 \(y=ax^2+bx\) 过 \(x=x_0,\ y\in[y_1,y_2]\) 当且仅当:
\[\dfrac{y_1}{x_0}\le ax_0+b\le\dfrac{y_2}{x_0} \]不等号两个方向分别是一个半平面,跑半平面交判断即可 .
Minkowski 和
定义:两个凸包 \(A,B\) 的 Minkowski 和 \(C=\{a+b\mid a\in A,b\in B\}\) .
就是相当于对于凸包 \(A\) 沿着 \(B\) 的每个向量移动后得到的所有位置的并 .
做法不是很困难,极角排序后归并就行了 . 如果有三点共线情况还需要再求一次凸包 .
JSOI2018 战争
给两个凸多边形 \(A,B\),若干次操作,每次将 \(B\) 平移一下,操作后问 \(A,B\) 是否有交 .
\(A,B\) 的点数和操作次数均不大于 \(10^5\) .
Solution
设 \(A,B\) 上有点 \(a,b\),那么移动向量 \(\bm v\) 满足有交当且仅当存在 \(b+\bm v=a\) .
可以写成 \(\bm v=a-b\),Minkowski 和算 \(A+(-B)\) 就行了 .
杂项
三维计算几何部分我就不写了 .
Pick 定理
顶点均为整点的简单多边形,面积 \(A\)、内部格点数和边上格点数满足 \(A=i+\frac b2-1\) .
最小圆覆盖
最小圆覆盖:平面上若干个点,找一个最小的圆包含所有点 .
暴力:枚举三个点 \(i,j,k\) 组成一个圆,两个点 \(i,j\) 作为直径组成一个圆 .
优化:目前枚举到的点不能在最优圆内 .
然后随机打乱复杂度就对了 .
平面最近点对
cdq 分治双指针,复杂度是 \(O(n\log n)\) 或者 \(O(n\log^2n)\) 的 .
关于复杂度可以发现的是某个点周围有用的点不会很多:
标签:直线,QAQ,cdot,Max,线段,凸包,多边形,几何,theta From: https://www.cnblogs.com/CDOI-24374/p/17614518.html