【整理】算法竞赛计算几何学习笔记

二维基础

特殊值与精度

  • 无穷 $1.0/0.0=\operatorname{INFINITY},1.0/0.0=\operatorname{-INFINITY}$
  • 非数 $0.0/0.0 =\operatorname{NAN}$
    • 要注意,$\operatorname{NAN} (\ge,\le,>,<,= ) x$ 结果均为 False,只有 $\operatorname{NAN} \neq x$ 结果才为 True
  • $+0.0,-0.0$ 也是一类特殊值,因而我们在比较时需要加入容限 eps。
  • 特别的,频繁使用数学函数(开方,三角函数)等容易造成精度丢失,尽量减少使用。

例题:计算几何spj hacker

点与向量

点的定义方法:struct Point {double x,y;};

向量的定义方法:using Vector=Point;(直接使用 Point 亦可)

  • 向量点积: $\vec{a}\cdot\vec{b}=a_xb_x+a_yb_y$
    • 几何意义:$\vec{a} \cdot \vec{b} = \left | \vec{a} \right | \left | \vec{b} \right | \cos \theta$​
    • 向量的长度:$|\vec{a}| = \sqrt{\vec{a} \cdot \vec{a} }$
    • 向量的夹角:$\cos\theta=\frac{\vec{a}\cdot\vec{b}}{|\vec{a}||\vec{b}|}$
    • 向量的投影:$|\vec{a}|\cos\theta=\frac{\vec{a}\cdot\vec{b}}{|\vec{b}|}$
    • 向量垂直:$\vec{a} \cdot \vec{b} = 0$​
  • 向量叉积:$\vec{a}\times\vec{b}=(a_xb_y-a_yb_x)\widehat{k}$​
    • 注:$\widehat{k}$ 表示 $\vec{k}$ 是一个单位向量。

    • 几何意义$:\vec{a}\times\vec{b}=|\vec{a}|\left|\vec{b}\right|\sin\theta\widehat{k}$

    • 平行四边形面积:$|\vec{a}||\vec{b}||\sin\theta|=|\vec{a}\times\vec{b}|$

    • 向量平行:$\vec{a} \times \vec{b} = \vec{0}$

  • to-left 测试判断点 $P$ 在有向直线 $AB$ 左侧/右侧/上

    • $\begin{cases}\overrightarrow{AB}\times\overrightarrow{AP}>0,&P\text{在有向直线}AB\text{左侧}\\overrightarrow{AB}\times\overrightarrow{AP}<0,&P\text{在有向直线}AB\text{右侧}\\overrightarrow{AB}\times\overrightarrow{AP}=0,&P\text{在有向直线}AB\text{上}\end{cases}$
  • 向量 $\vec{a}$ 逆时针旋转 $\theta$
    • $\begin{bmatrix}\cos\theta&-\sin\theta\\sin\theta&\cos\theta\end{bmatrix}\begin{bmatrix}a_x\a_y\end{bmatrix}=\begin{bmatrix}\cos\theta a_x-\sin\theta a_y\\sin\theta a_x+\cos\theta a_y\end{bmatrix}$​

例题:OperationLove

线段

定义方法:struct Segment {Point a,b;};

  • 判断点 $P$ 是否在线段 $AB$ 上:
    1. 点 $P$ 在 $AB$ 所在直线上:$\vec{PA}\times\vec{PB}=\vec{0}$。
    2. 点 $P$ 在 $AB$ 之间:$\vec{PA}\cdot \vec{PB} \le 0 $ 或 $\begin{cases}\min{A_x,B_x}\leq P_x\leq\max{A_x,B_x}\\min{A_y,B_y}\leq P_y\leq\max{A_y,B_y}\end{cases}$​
  • 判断线段 $AB$ 和 $CD$ 是否相交(两种可能):
    1. 点 $A$ 和点 $B$ 在直线 $CD$ 的不同侧,且点 $C$ 和点 $D$ 在直线 $AB$​ 的不同侧(使用 to-left 测试)
    2. 三点共线或四点贡献(验证是否有某线段的端点在另一线段上的情况)

例题:Magic Rabbit

直线

定义方法: struct Line {Point p,v;};(点向式,特别地,控制 $\vec{OP}+\lambda \vec{v}$ 中 $\lambda$ 的取值范围,该式子也可以用于表示线段或射线)。

多边形

定义方法:struct Polygon {vector<Point> p;};

  • 一般情况下,按逆时针顺序排列点。
  • 多边形面积 $S=\frac12\left|\sum_{i=0}^{n-1}\overrightarrow{OP_i}\times\overrightarrow{OP_{(i+1)\operatorname{mod}n}}\right|$,点 $O$ 在多边形内外均可。
  • 判断点是否在多边形内:
    1. 光线投射算法:从该点引出一条射线(通常取水平线或竖直线),如果这条射线与多边形有奇数个交点,则该点在多边形内部,否则该点在多边形外部(交点为多边形顶点时,将该顶点视作在射线上侧,即所有边界的上端点和下端点只有一个是视作有效的)。
    • 需要特判点在多边形上的情况
      1. 回转数法:面内闭合曲线逆时针转圈,闭合曲线绕过该点的总次数称为回转数。当回转数为 $0$,点在曲线外部。
    • 一种实现方式是计算相邻两边夹角的和,注意夹角是有方向的。
      1. 凸多边形:$n$ 次 to-left 测试。

定义方法:struct Circle {Point c; double r;};

本文作者:water_tomato
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇