仍在更新中…..

计算几何

没正式学过。。胎教组选手 yijan

基础操作

加减乘除、点积叉积

首先我们定义点，显然点的定义直接用坐标

struct Point {
    double x , y;
    Point( double x = 0 , double y = 0 ): x(x) , y(y) {}
};

然后，一般矢量使用坐标表示，标记为 $\vec v = (x,y)$ ，直接把点看成矢量也可。

定义一下基本运算，包括向量加减、数乘：

inline Point operator + ( const Point& a , const Point& b ) {
    return Point( a.x + b.x , a.y + b.y );
}
inline Point operator - ( const Point& a , const Point& b ) {
    return Point( a.x - b.x , a.y - b.y );
}
inline Point operator * ( const Point& a , const double b ) {
    return Point( a.x * b , a.y * b );
}
inline Point operator / ( const Point& a , const double b ) {
    return Point( a.x / b , a.y / b );
}

然后是点积和叉积，定义 $ \theta = \cos\langle \vec a , \vec b \rangle $ ，即 $ \vec a,\vec b $ ，的夹角，于是叉积、点积定义如下：

其中点积、叉积均满足分配律，均不满足结合律，点积满足交换律，叉积满足反交换律。反交换律是指：

$\vec a \times \vec b = - \vec b \times \vec a$

关于他们的几何意义，点积是其中一个向量在另一个向量上投影长度乘以另一个向量的长度，叉积是两个向量的有向面积。具体而言，叉积的绝对值就是两个向量共起点时作为邻边构成的平行四边形面积，而叉积的符号（方向）取决于：

若 $ \vec b $ 在 $ \vec a $ 的逆时针方向，那么 $ \vec a \times \vec b $ 符号为正
否则 $ \vec a \times \vec b $ 符号为负

关于代码：

inline double dot( const Point& a , const Point& b ) {
    return a.x * b.x + a.y * b.y;
}
inline double det( const Point& a , const Point& b ) {
    return a.x * b.y - a.y * b.x;
}

旋转矩阵

将 $\vec v(x,y)$ 旋转 $\theta$ ，相当于：

$\left[ \begin{matrix} x\\ y \end{matrix} \right] \left[\begin{matrix}\cos \theta & -\sin \theta \\ \sin \theta & \cos \theta\end{matrix}\right]$

得到的是 $\vec v’ = (x\cos \theta - y\sin \theta , x\sin \theta + y\cos \theta)$

线段相交

给定两个线段 $AB,CD$ 如何判断它们是否相交？

判断线段相交分两步：

快速排斥实验

首先判断两个线段在 $x,y$ 坐标轴上的投影是否有重合，如果这个都没有重合显然不会相交
计算叉积

如果两个线段的投影有重合，我们可以直接判断 $C,D$ 是否在 $AB$ 的两侧以及 $A,B$ 是否在 $CD$ 的两侧。这个的判断用到了前面的叉积：
$(\overrightarrow {AC}\times \overrightarrow {AB})\cdot (\overrightarrow{AD}\times \overrightarrow {AB}) \le 0$
这个式子等价于 $C,D$ 在 $AB$ 的两侧。

极角排序

顾名思义，按照某个点的极角排序。

怎么比较两个点到某个点的极角呢？考虑要比较 $A,B$ 到 $O$ 的极角大小，我们算出 $\overrightarrow{OA}\times\overrightarrow{OB}$ ，如果值为 0 ，即三点共线，不需要比较，否则如果为负数，则 $A$ 在 $B$ 的顺时针方向，极角小于 $B$ ，否则为正数就是反过来。

判断符号正负最好这么写：

1
2
3

int sgn( const double& x ) {
    return fabs( x ) <= eps ? 0 : ( x < 0 ? -1 : 1 );
}

然后极角排序的比较函数：

Point A[MAXN];
Point p;
bool cmp( Point a , Point b ) {
    double t = det( a - p , b - p );
    if( sgn( t ) == 0 ) return dist( a , p ) < dist( b , p );
    return sgn( t ) > 0;
}

例题

多边形的面积

对于每一条边 $AB$ ，考虑原点为 $O$ ，那么直接 $\sum \frac{\overrightarrow {OA}\times \overrightarrow{OB}}{2}$ 就行了，也就是对于每个边将它和原点的三角形的有向面积加起来，注意必须要按照同一个方向，顺时针逆时针都可以。

至于为什么。。稍微画个图验证一下就会了。

圆和多边形的交

给出一个圆和一个 $n$ 个点的多边形, 求它们交的面积, 要求复杂度 $O(n)$。

类似前面的思路，我们把多边形拆成很多个三角形，现在就是求三角形和圆的交的面积。

然后我们把圆移到原点，大力分类讨论。分类的依据是 $\triangle OAB$ 中 $AB$ 这个边和圆的交点个数。分类讨论部分由于懒得画图就引用卢爷的讲义了：

情况 1

$AB$ 与圆有 $0$ 个交点，$A,B$ 都在圆内

交就是三角形的面积

情况 2

$AB$ 与圆有 $0$ 个交点，$A,B$ 都在圆外

交为扇形 $OCD$

情况 3

$AB$ 与圆有 $1$ 个交点，$A$ 在圆内，$B$ 在圆外

交为三角形 $OAC$ 和扇形 $OCD$

情况 4

$AB$ 与圆有 $1$ 个交点，$A,B$ 在圆外

交为扇形 $ODE$

情况 5

$AB$ 与圆有 $2$ 个交点，$A,B$ 在圆外

交为扇形 $OEF$ 与三角形 $OCE,ODF$

扇形面积计算可以用余弦定理。