2019暑期金华集训 Day6 计算几何
自闭集训 Day6
计算几何
内积
内积不等式:
\[
(A,B)^2\le (A,A)(B,B)
\]
其中\((A,B)\)表示\(A\cdot B\)。
(好像是废话?)
叉积
\[
A\times B=|A||B|\sin \theta
\]
二维叉积:\(A\times B=x_1y_2-x_2y_1\)。
三维叉积:
\[
A\times B=\left|
\begin{matrix}
i&j&k\\
Ax&Ay&Az\\
Bx&By&Bz
\end{matrix}
\right|
\]
叉积判直线关系:??
极角
atan2(y,x)
,返回值\((-\pi,\pi]\)。
如果极角相差较大可以用这个来判,否则由于精度问题可能要用叉积。在值域\(10^9\)的时候这个函数可能基本没用。
旋转
向量的旋转,直接用三角函数公式推一推即可,可以写成矩阵的形式。
经典题
每时刻有旋转/平移/缩放等操作,问一个向量在\([l,r]\)中操作之后会变成什么。
直接写成矩阵乘法的形式,用线段树维护。
Simpson积分
对于二次函数\(f(x)\),有
\[
\int_{x=l}^r f(x)\mathrm dx=\frac{(r-l)(f(l)+f(r)+4f((l+r)/2))}{6}
\]
对于其他函数,可以用二次函数拟合。
Projection
求\(P\)在直线\(P_1P_2\)上的投影点/对称点。
直接把直线\(P_1P_2\)的垂线做出来,求个交,就没了。
也可以用点积得到\(PP_1\)在\(P_1P_2\)上的投影长度,然后也可以求出垂足。
向量的位置关系
直接点积叉积乱搞一通就没了。
直线的位置关系、线段的位置关系都差不多。
线段是否相交
先把直线平行、直线重合判掉。
然后分别把两条线段的端点取出来,看是否在另一条直线的两边。
(老师给的方法:先判外接矩形是否相交,然后再做跨立实验)
线段交点
把直线重合判掉,然后当成直线来求交点。
线段之间距离
距离定义为最近点对的距离。
如果有交点则为0,否则变成点到线段距离。
点到线段距离?点积判一下端点之间位置关系然后直接做。
多边形面积
不保证多边形是凸的。
直接在二维平面上随便选一个点然后叉积。
判凸包
直接叉积就没了。
判点在多边形内
射线法大家都知道,但有很多恶心的边界情况。
两种方法:
第一种:把斜率设成一个奇怪的无理数,多半可以跳过所有边界情况。
第二种:钦定射线向右,把所有边界情况都判了就完事了。
边界:
- 如果射线与边重合那么
continue
。 - 如果穿过了\(AB\)的\(A\),而且\(AB\)向下,那么计数器++。
- 如果穿过了\(AB\)的\(B\),而且\(AB\)向上,那么计数器++。
- 如果点在边上那么直接返回。
求凸包
大家都会?
求凸包直径
旋转卡壳。
求凸包在射线左边的面积
把有关的点抠出来,仍然是一个凸包,然后算面积即可。
平面最近点对距离
K-D Tree多好
分治,然后发现左边匹配右边只会有\(O(1)\)个点有可能产生贡献,于是没了。
圆的关系
相离,外切,相交,内切,内含。
圆心和半径的关系乱搞即可。
求圆和直线的交点
知道半径、知道圆心到直线的距离,于是可以得到弦长,于是没了。
求两个圆的交点
可以求出交点的直线方程,于是没了。
当然,也可以用余弦定理解三角形得到答案。
点到圆的切点
知道半径、知道距离、知道有一个直角,于是可以解三角形。
两个圆的公切线
首先判掉内含、内切。
此时必然有两条外公切线,解一解三角形。
内公切线类似。
求圆和多边形交的面积
可以通过有向面积化成三角形和圆的交的面积。注意到三角剖分的原点任意,可以设为圆心。
如果三个点都在里面那么很容易。
否则就把线段\(AB\)与圆的交点搞出来,把三角形切开,递归搞。
只会递归常数层,但比较好写。
bzoj1043
直接暴力,对于每个圆盘求出后面的圆盘盖掉它的角度区间,求个区间并就没了。
角度区间可以求圆的交点来求。
CF932F
设\(dp_x\)表示从\(x\)跳到某个叶子的最小代价,从下往上DP。
每次求\(x\)的答案的时候发现就是一个斜率优化,启发式合并把子树内的凸包合起来就没了。
DSU on tree维护凸包也可以。
然后就是要支持往凸包里插入一个点,拿set乱搞即可。
某题
发现最多选4个向量,而且选4个向量的时候只能是互相垂直的,可以判掉。于是只要选3个向量,使得相邻两个向量的夹角小于180。
然后把所有向量反向再加进去,正向的设为红色,反向的设为绿色。
于是我们就要找形如“红绿红”的三条向量,并且两个红向量的夹角小于180。
枚举第一个红向量,数据结构维护后面两个的最小值。
CF1025F
结论:三角形不相交等价于能做出两条内公切线。
然后枚举一条公切线,答案就是公切线两边分别选两个点的方案数。
bzoj2961
圆反演,点在圆内转化为点在直线的某一侧。
于是变成动态半平面交,也许可以转化为凸包做?
圆反演
对于一个点\(P\),如果\(P\)对\(O\)反演,那么\(P\)仍然在射线\(OP\)上,距离变为原来的倒数。
一条不过\(O\)的直线反演后变成一个过\(O\)的圆,反之亦然。
不过\(O\)的圆反演后仍然是不过\(O\)的圆。
HDU4773
圆反演,就变成了求两个圆的某个特定公切线。(注意原题需要外切,所以不能乱搞公切线)
Codechef QPOINT
注意“不相交”也保证了两个多边形不能相互包含。
考虑射线法,看一个点往上对着的第一个线段,如果是从右往左那么就在多边形外,否则在多边形内。(假设边是按顺时针走的)
如果可以离线,那么按\(x\)排序一下从左往右搞,因为没有相交的边,所以用set很好维护。
不能离线,那么用可持久化treap维护。
细节很多,也许旋转某个无理数角度会有点用?
CF704E
树剖,把树上的问题转化为序列上的问题。
以时间为\(x\)轴、位置\(y\)轴,那么一次位移就是二维平面的一条线段。
问题就转化为\(m\log n\)条线段什么时候最早相交。
按\(x\)坐标扫描线,用\(set\)维护所有线段的\(y\)的相对大小关系。
如果两条线段有交,那么他们一定会有某个时刻在set里是相邻的。
又因为我们只需要求最早的交点,所以我们可以认为set里面的线段永远不相交,因为当我们跑到相交的时间的时候就要直接返回答案了。
于是每次加入一条线段的时候判一下和前驱后继相交的时间,更新一下结束时间。如果当前时间超出了结束时间那么就可以直接返回了。
CF799G
设\(f(x)\)表示极角为\(x\)的射线左边面积减去右边面积,那么有\(f(0)=-f(\pi)\)。
所以中间必然存在零点,可以二分这个零点。
考虑二分了一个极角之后怎么求\(f(x)\)。可以使用二分得到这条射线与凸包的各种交点,然后用各种前缀和得到面积,所以可以\(O(\log n)\)得到\(f(x)\)。
所以我们\(O(n\log^2 n)\)做出了答案。
(听起来细节就特别特别多……)
最新文章
- 面向对象(Object-Oriented)
- spring mvc文件上传
- dubbo服务自动化测试搭建
- jQuery自定义插件
- ViewController respondsToSelector:]: message sent to deallocated instance
- vs2010:fatal error LNK1123: 转换到 COFF 期间失败
- 导入maven工程遇见的问题【问题】
- SQL Server 2012 使用警报调度数据库作业通知操作员
- crossplatform---Nodejs in Visual Studio Code 09.企业网与CNPM
- Linux File、File Directory IO Operation Summary(undone)
- IIS CS0016: 未能写入输出文件“c:\WINDOWS\Microsoft.NET\Framework\.。。”--“拒绝访问
- change
- Android Studio快捷键指南(本文持续更新)
- [bzoj 2243]: [SDOI2011]染色 [树链剖分][线段树]
- Linux命令top 详解
- 团队作业6——展示博客(Alpha版本)
- IntellIJ IDEA 配置 Maven 以及 修改 默认 Repository
- android 缩放平移自定义View 显示图片
- RabbitMQ可靠性投递及高可用集群
- 自制操作系统Antz(13) 显示图片