开始之前
圆周率
const pi = acos(-1);
浮点数的比较
对实数进行浮点运算难免会出现精度误差
为了控制精度，可以设置一个偏差值\(eps\)
const double eps = 1e-5;
int sgn(double x)
{
if (fabs(x) < eps) return 0;
return x < 0 ? -1 : 1;
}
int dcmp(double x, double y)
{
if (fabs(x - y) < eps) return 0;
return x < y ? -1 : 1;
}
点
点的表示
二维下点用\((x, y)\)表示
struct Point
{
double x, y;
Point(){};
Point(double x, double y):x(x), y(y){}
};
点与点之间的距离
- 使用库函数\(hypot()\)
double Dis1(Point A, Point B)
{
return hypot(A.x - B.x, A.y - B.y);
}
- 使用\(sqrt()\)
double Dis2(Point A, Point B)
{
return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}
向量
向量的表示
有大小和方向的量称为向量（矢量），向量用平面上两个点——起点\(P1\)和终点\(P2\)表示
向量只是一个量而不是线段，因此可以随意的移动，为了方便可以把向量的起点移动到原点，这样向量可用一条由原点到一点\((x, y)\)的有向线段表示
向量在表示上与点的表示相同
typedef Point Vector;
向量的运算
- 加减乘除
Point operator + (Point B) {return Point(x + B.x, y + B.y);}
Point operator - (Point B) {return Point(x - B.x, y - B.y);}
Point operator * (double k) {return Point(x * k, y * k);}
Point operator / (double k) {return Point(x / k, y / k);}
- 等于
bool operator == (Point B) {return !sgn(x - B.x) && !sgn(y - B.y);}
点乘
- 定义
向量\(A\)和\(B\)的点乘\(A \cdot B = |A||B|cos \theta\)，\(\theta\)为\(A\)、\(B\)之间的夹角
点乘的几何意义是求\(A\)在\(B\)上的投影长度乘以\(B\)的模长
若已知\(A(A.x, A.y)\)，\(B(B.x, B.y)\)，有\(A \cdot B = A.x \times B.x + A.y \times B.y\)
double Dot(Vector A, Vector B) {return A.x * B.x + A.y * B.y;}
- 判断夹角
可根据点乘的正负判断夹角是锐角，直角，还是钝角：
若\(A \cdot B > 0\)且\(A \cdot B \neq 1\)，\(A\)、\(B\)之间的夹角为锐角；
若\(A \cdot B < 0\)且\(A \cdot B \neq -1\)\(，\)A\(、\)B$之间的夹角为钝角；
若\(A \cdot B = 0\)，\(A\)、\(B\)之间的夹角为直角；
若\(A \cdot B = 1\)，\(A\)、\(B\)方向相同；
若\(A \cdot B = -1\)，\(A\)、\(B\)方向相反
- 求向量的长度
double Len(Vector A) {return sqrt(Dot(A, A));} // 长度
double Len2(Vector A) {return Dot(A, A);} // 长度的平方
- 求夹角
double Angle(Vector A, Vector B) {return acos(Dot(A, B) / Len(A) / Len(B));}
叉乘
- 定义
向量\(A\)和\(B\)的叉乘\(A \times B = |A||B|sin \theta\)，\(\theta\)为向量\(A\)旋转到向量\(B\)所经过的夹角
叉乘的几何意义是向量\(A\)与向量\(B\)形成的平行四边形的有向面积
若已知\(A(A.x, A.y)\)，\(B(B.x, B.y)\)，有\(A \times B = A.x \times B.y - A.y \times B.x\)
double Cross(Vector A, Vector B) {return A.x * B.y - A.y * B.x;}
注意叉乘有正负，\(A \times B\) 与 \(B \times A\)相反
- 判断向量A，B的方向关系
可根据叉乘的正负判断\(B\)在\(A\)的什么方向：
若\(A \times B > 0\)，\(B\)在\(A\)的逆时针方向；
若\(A \times B < 0\)，\(B\)在\(A\)的顺时针方向；
若\(A \times B = 0\)，\(A\)与\(B\)共线，可能方向相同，可能方向相反
- 计算平行四边形面积
三个点\(A\)、\(B\)、\(C\)，可求以\(A\)为公共点得到的两个向量\(B - A\)、\(C - A\)构成的平行四边形面积
double Area2(Point A, Point B, Point C) {return fabs(Cross(B - A, C - A));}
- 计算三角形面积
可求由三个点\(A\)、\(B\)、\(C\)构成的\(\Delta ABC\)的面积
double Area(Point A, Point B, Point C) {return Area2(A, B, C) / 2;}
- 判断向量是否共线
bool Parallel(Vector A, Vector B) {return !sgn(Cross(A, B));}
向量旋转
使向量\(A(x, y)\)绕起点逆时针旋转\(\theta\)，旋转后的向量为\(A^{'}(x^{'}, y^{'})\)
\(x^{'} = xcos\theta - ysin\theta\)，\(y^{'} = xsin\theta + ycos\theta\)
Vector Rotate(Vector A, double rad) {return Vector(A.x * cos(rad) - A.y * sin(rad), A.x * sin(rad) + A.y * cos(rad));}
- 求单位法向量
可以用\(Rotate()\)求
Vector Normal1(Vector A) {return Rotate(A, pi / 2) / Len(A);}
由于旋转\(90^\circ\)很特殊，也可以直接写
Vector Normal2(Vector A) {return Vector(-A.y / Len(A), A.x / Len(A));}