一、基础知识

1. \(\pi = \arccos(-1)\)

2. 余弦定理 \(c^2=a^2+b^2-2ab\cos\theta\)

3. 浮点数的比较

   const double eps=1e-8;
   int sign(double x) {
       if (fabs(x) < eps) return 0;
       if (x < 0) return -1;
       return 1;
   }
   

   int cmp(double x, double y) {
       if (fabs(x - y) < eps) return 0;
       if (x < y) return -1;
       return 1;
   }
   

4. 向量

   1. 内积、点积

      double dot(Point a, Point b) {
          return a.x * b.x +a.y * b.y;
      }
      

   2. 外积、叉积

      double cross(Point a, Point b) {
          return a.x * b.y - b.x * a.y;
      }
      

   3. 向量长度 sqrt(dot(a, a));

   4. 向量夹角 acos(dot(a, b) / get_length(a) / get_length(b));

   5. 平行四边形面积 cross(b - a, c - a);

   6. 向量旋转（顺时针）

      \[\begin{bmatrix}x&y\end{bmatrix}\times\begin{bmatrix}\cos\theta&-\sin\theta\\\sin\theta&\cos\theta\end{bmatrix} \]

5. 直线

   1. 点向式 \(\boldsymbol{v}t+P_0\)。

   2. 判断点在直线上 \(\boldsymbol{A}\times\boldsymbol{B}=0\)。

   3. 相交

      Point get_line_intersection(Point p, Vector v, Point q, Vector w) {
          Vector u = p - q;
          double t = cross(w, u) / cross(v, w);
          return p + v * t;
      }
      

   4. 点到直线距离

      double distance_to_line(Point p, Point a, Point b) {
          Vector v1 = b - a, v2 = p - a;
          return fabs(cross(v1, v2) / get_length(v1));
      }
      

   5. 点到线段距离

      double distance_to_segment(Point p, Point a, Point b) {
          if (a == b) return get_length(p - a);
          Vector v1 = b - a, v2 = p - a, v3 = p - b;
          if (sign(dot(v1, v2)) < 0) return get_length(v2);
          if (sign(dot(v1, v3)) > 0) return get_length(v3);
          return distance_to_line(p, a, b);
      }
      

   6. 点在直线上投影

      double get_line_projection(Point p, Point a, Point b) {
          Vector v = b - a;
          return a + v * (dot(v, p - a) / dot(v, v));
      }
      

   7. 点是否在线段上

      bool on_segment(Point p, Point a, Point b) {
          return sign(cross(p - a, p - b)) == 0 && sign(dot(p - a, p - b)) <= 0;
      }
      

   8. 判断两线段是否相交

      bool segment_intersection(Point a1, Point a2, Point b1, Point b2) {
          double c1 = cross(a2 - a1, b1 - a1), c2 = cross(a2 - a1, b2 - a1);
          double c3 = cross(b2 - b1, a2 - b1), c4 = cross(b2 - b1, a1 - b1);
          return sign(c1) * sign(c2) <= 0 && sign(c3) * sign(c4) <= 0;
      }
      

6. 三角形

   1. 面积：叉积、海伦公式：

      \[p = (a+b+c) / 2\S = \sqrt{p(p-a)(p-b)(p-c)} \]

   2. 外心、内心、垂心、重心

      重心是到三角形三顶点距离平方和最小的点，三角形内到三边距离之积最大的点。

7. 普通多边形（通常按逆时针方向存储所有顶点）

   1. 求多边形面积：

      double polygon_area(Point p[], int n) {
          double s = 0;
          for (int i = 1; i < n - 1; ++ i) 
              s += cross(p[i] - p[0], p[i + 1] - p[0]);
          return s / 2;
      }
      

   2. 判断点是否在多边形里

      射线法

      从该点出发任意做一条和所有边都不平行的射线。交点个数为偶数，则在多边形外；为奇数，则在多边形内。

   3. 判断点是否在凸多边形内

      只需判断点是否在所有边左边

   4. 皮克定理（顶点在格点上）

      \[S=a+b/2+1 \]

      \(a\) 表示多边形内部的点数，\(b\) 表示多边形边上的点数

计算几何相关总结

原文：https://www.cnblogs.com/little-aztl/p/14818084.html