ACM模板计算几何

二维几何

基本运算

const double eps = 1e-12;
const double PI = acos(-1);
// 判断正负
int sgn(double x) { return fabs(x) < eps ? 0 : (x < 0 ? -1 : 1); }
// 弧度转角度
double R_to_D(double rad) { return 180 / PI * rad; }
// 角度转弧度
double D_to_R(double D) { return PI / 180 * D; }

struct Point {
  double x, y;
  Point(double _x = 0, double _y = 0) : x(_x), y(_y) {}
};
typedef Point Vector;
// 向量 + 向量 = 向量, 点 + 向量 = 向量
Vector operator + (Vector A, Vector B) { return Vector(A.x + B.x, A.y + B.y); }
// 点 - 点 = 向量(向量BC = C - B)
Vector operator - (Point A, Point B) { return Vector(A.x - B.x, A.y - B.y); }
// 向量 * 数 = 向量
Vector operator * (Vector A, double p) { return Vector(A.x * p, A.y * p); }
// 向量 / 数 = 向量
Vector operator / (Vector A, double p) { return Vector(A.x / p, A.y / p); }
// 点,向量比较函数
bool operator < (Point A, Point B) { return A.x < B.x || (!sgn(A.x - B.x) && A.y < B.y); }
bool operator == (Point A, Point B) { return !sgn(A.x - B.x) && !sgn(A.y - B.y); }
// 求极角(极坐标系中,平面上任何一点到极点的连线和极轴的夹角叫做极角),弧度制
double Polar_angle(Vector A) { return atan2(A.y, A.x); }
// 点积(满足交换律)
double Dot(Vector A, Vector B) { return A.x * B.x + A.y * B.y; }
// 叉积(不满足交换律),Cross(x, y) = -Cross(y, x)
double Cross(Vector A, Vector B) { return A.x * B.y - B.x * A.y; }
// 判断向量bc是不是向量ab的逆时针方向(左边),也可看作点c是否在向量ab左边
bool ToLeftTest(Point A, Point B, Point C) { return sgn(Cross(B - A, C - B)) > 0; }
// 向量取模,求长度
double Length(Vector A) { return sqrt(Dot(A, A)); }
// 计算两向量夹角,弧度制
double Angle(Vector A, Vector B) { return acos(Dot(A, B) / Length(A) / Length(B)); }
// 计算两向量构成的平行四边形面积(交点为A的两向量AB,AC)
double Area2(Point A, Point B, Point C) { return Cross(B - A, C - A); }
// 计算向量逆时针旋转90°后的单位法线(法向量)
Vector Normal(Vector A) { return Vector(-A.y / Length(A), A.x / Length(A)); }
// 计算向量逆时针旋转rad后的向量
Vector Rotate(Vector A, double rad) {
  return Vector(A.x * cos(rad) - A.y * sin(rad), A.x * sin(rad) - A.y * cos(rad));
}
// 点A绕点B顺时针旋转rad
Point turn_PP(Point A, Point B, double rad) {
  return Point((A.x - B.x) * cos(rad) + (A.y - B.y) * sin(rad) + B.x,
               -(A.x - B.x) * sin(rad) + (A.y - B.y) * cos(rad) + B.y);
}

点和直线

struct Line {
  Vector v;
  Point p;
  Line(Vector _v, Point _p) : v(_v), p(_p) {}
  Point get_point_in_line(double t) { return v + (p - v) * t; }
};
// 点(C)和直线(AB)的关系,1在左侧,-1在右侧,0在直线上
int relation(Point A, Point B, Point C) {
  int c = sgn(Cross(B - A, C - A));
  return c < 0 ? 1 : (c > 0 ? -1 : 0);
}
// 计算两直线交点,当且仅当Cross(v, w) != 0
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;
}
// 计算点(P)到直线(AB)的距离
double Distance_point_to_line(Point P, Point A, Point B) {
  Vector v1 = B - A, v2 = P - A;
  return fabs(Cross(v1, v2) / Length(v1));
}
// 计算点(P)到线段(AB)的距离
double Distance_point_to_segment(Point P, Point A, Point B) {
  if (A == B) return Length(P - A);
  Vector v1 = B - A, v2 = P - A, v3 = P - B;
  if (sgn(Dot(v1, v2)) < 0) return Length(v2);
  if (sgn(Dot(v1, v3)) > 0) return Length(v3);
  return fabs(Cross(v1, v2) / Length(v1));
}
// 求点(P)在直线(AB)的投影点
Point Get_line_projection(Point P, Point A, Point B) {
  Vector v = B - A;
  return A + v * (Dot(v, P - A) / Dot(v, v));
}
// 求点(P)到直线(AB)的垂足
Point FootPoint(Point P, Point A, Point B) {
  Vector x = P - A, y = P - B, z = B - A;
  double len1 = Dot(x, z) / Length(z), len2 = -1.0 * Dot(y, z) / Length(z);
  return A + z * (len1 / (len1 + len2));
}
// 求点(P)在直线(AB)的对称点
Point Symmetry_PL(Point P, Point A, Point B) {
  return P + (FootPoint(P, A, B) - P) * 2;
}
// 判断点(P)是否在线段(AB)上
bool OnSegment(Point P, Point A, Point B) {
  return !sgn(Cross(A - P, B - P)) && sgn(Dot(A - P, B - P)) < 0;
}
// 判断两线段是否相交
bool Segment_proper_intersection(Point A, Point B, Point C, Point D) {
  double a = Cross(B - A, C - A), b = Cross(B - A, D - A);
  double c = Cross(D - C, A - C), d = Cross(D - C, B - C);
  // if是否允许在端点处相交,根据需要增加
  if (!sgn(a) || !sgn(b) || !sgn(c) || !sgn(d)) {
    bool f1 = OnSegment(C, A, B);
    bool f2 = OnSegment(D, A, B);
    bool f3 = OnSegment(A, C, D);
    bool f4 = OnSegment(B, C, D);
    bool f = f1 | f2 | f3 | f4;
    return f;
  }
  return sgn(a) * sgn(b) < 0 && sgn(c) * sgn(d) < 0;
}

某个大佬的板子

#include <bits/stdc++.h>
using namespace std;

const double PI       = acos(-1);
const double INF      = 1e10;  // 无穷大
const double eps      = 1e-15; // 计算精度
const int LEFT        = 0;     // 点在直线左边
const int RIGHT       = 1;     // 点在直线右边
const int ONLINE      = 2;     // 点在直线上
const int CROSS       = 0;     // 两直线相交
const int COLINE      = 1;     // 两直线共线
const int PARALLEL    = 2;     // 两直线平行
const int NOTCOPLANAR = 3;     // 两直线不共面
const int INSIDE      = 1;     // 点在图形内部
const int OUTSIDE     = 2;     // 点在图形外部
const int BORDER      = 3;     // 点在图形边界
const int BAOHAN      = 1;     // 大圆包含小圆
const int NEIQIE      = 2;     // 内切
const int XIANGJIAO   = 3;     // 相交
const int WAIQIE      = 4;     // 外切
const int XIANGLI     = 5;     // 相离

struct Point {  // 二维点或矢量
  double x, y;
  double angle, dis;
  Point() {}
  Point(double _x, double _y) : x(_x), y(_y) {}
};
struct Point3D {  // 三维点或矢量
  double x, y, z;
  Point3D() {}
  Point3D(double _x, double _y, double _z) : x(_x), y(_y), z(_z) {}
};
struct Line {  // 二维直线或线段
  Point p1, p2;
  Line() {}
  Line(Point _p1, Point _p2) : p1(_p1), p2(_p2) {}
};
struct Line3D {  // 三维直线或线段
  Point3D p1, p2;
  Line3D() {}
  Line3D(Point3D _p1, Point3D _p2) : p1(_p1), p2(_p2) {}
};
struct Rect {  // 用长宽表示矩形 w,h分别为宽和高
  double w, h;
  Rect() {}
  Rect(double _w, double _h) : w(_w), h(_h) {}
};
struct Rect_2 {  // 表示矩形,左下角(xl, yl),右上角(xh, yh)
  double xl, yl, xh, yh;
  Rect_2() {}
  Rect_2(double _xl, double _yl, double _xh, double _yh)
    : xl(_xl), yl(_yl), xh(_xh), yh(_yh) {}
};
struct Circle {  // 圆
  Point c;
  double r;
  Circle() {}
  Circle(Point _c, double _r) : c(_c), r(_r) {}
};
typedef vector<Point> Polygon;    // 二维多边形
typedef vector<Point> Points;     // 二维点集
typedef vector<Point3D> Points3D; // 三维点集

bool isZero(double x) {return fabs(x) < eps;}
bool isZero(Point p) {return isZero(p.x) && isZero(p.y);}
bool isZero(Point3D p) {return isZero(p.x) && isZero(p.y) && isZero(p.z);}
bool equal(double x, double y) {return fabs(x - y) < eps;}
bool lessThan(double x, double y) {return x < y && !equal(x, y);}
bool greaterThan(double x, double y) {return x > y && !equal(x, y);}
bool lessEqual(double x, double y) {return x < y || equal(x, y);}
bool greaterEqual(double x, double y) {return x > y || equal(x, y);}
double fix(double x) {return fabs(x) < eps ? 0 : x;}
// 二维矢量运算
bool operator==(Point p1, Point p2) {return equal(p1.x, p2.x) && equal(p1.y, p2.y);}
bool operator!=(Point p1, Point p2) {return !equal(p1.x, p2.x) || !equal(p1.y, p2.y);}
bool operator<(Point p1, Point p2) {return !equal(p1.x, p2.x) ? (p1.x < p2.x) : (p1.y < p2.y);}
Point operator+(Point p1, Point p2) {return Point(p1.x + p2.x, p1.y + p2.y);}
Point operator-(Point p1, Point p2) {return Point(p1.x - p2.x, p1.y - p2.y);}
// 叉积
double operator*(Point p1, Point p2) {return p1.x * p2.y - p2.x * p1.y;}
// 点积
double operator&(Point p1, Point p2) {return p1.x * p2.x + p1.y * p2.y;}
// 矢量的模
double norm(Point p) {return sqrt(p.x * p.x + p.y * p.y);}
// 把矢量p旋转角度angle(弧度),angle < 0顺时针,angle > 0逆时针
Point rotate(Point p, double angle) {
  Point result;
  result.x = p.x * cos(angle) - p.y * sin(angle);
  result.y = p.x * sin(angle) + p.y * cos(angle);
  return result;
}
// 三维矢量运算
bool operator==(Point3D p1, Point3D p2) {
  return equal(p1.x, p2.x) && equal(p1.y, p2.y) && equal(p1.z, p2.z);
}
bool operator<(Point3D p1, Point3D p2) {
  if (!equal(p1.x, p2.x)) return p1.x < p2.x;
  if (!equal(p1.y, p2.y)) return p1.y < p2.y;
  return p1.z < p2.z;
}
Point3D operator+(Point3D p1, Point3D p2) {
  return Point3D(p1.x + p2.x, p1.y + p2.y, p1.z + p2.z);
}
Point3D operator-(Point3D p1, Point3D p2) {
  return Point3D(p1.x - p2.x, p1.y - p2.y, p1.z - p2.z);
}
Point3D operator*(Point3D p1, Point3D p2) {  // 叉积
  return Point3D(p1.y * p2.z - p1.z * p2.y,
                 p1.z * p2.x - p1.x * p2.z,
                 p1.x * p2.y - p1.y * p2.x);
}
double operator&(Point3D p1, Point3D p2) {  // 点积
  return p1.x * p2.x + p1.y * p2.y + p1.z * p2.z;
}
double norm(Point3D p) {  //矢量的模
  return sqrt(p.x * p.x + p.y * p.y + p.z * p.z);
}
// 求面积
double area(Point A, Point B, Point C) {  // 三点求三角形面积
  return (B - A) * (C - A) / 2;
}
double area(double a, double b, double c) {  // 三条边求三角形面积
  double s = (a + b + c) / 2;
  return sqrt(s * (s - a) * (s - b) * (s - c));
}
double area(Circle C) {  // 圆面积
  return PI * C.r * C.r;
}
double area(const Polygon& poly) {  // 多边形面积
  double res = 0;
  int n = poly.size();
  if (n < 3) return 0;
  for (int i = 0; i < n; i++) {
    res += poly[i].x * poly[(i + 1) % n].y;
    res -= poly[i].y * poly[(i + 1) % n].x;
  }
  return res / 2;
}
// 点,线段,直线问题
double distance(Point p1, Point p2) {  // 二维两点距离
  return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}
double distance(Point3D p1, Point3D p2) {  // 三维两点距离
  return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y) + (p1.z - p2.z) * (p1.z - p2.z));
}
double distance(Point p, Line L) {  // 二维点到直线距离
  return fabs((p - L.p1) * (L.p2 - L.p1)) / norm(L.p2 - L.p1);
}
double distance(Point3D p, Line3D L) {  // 三维维点到直线距离
  return norm((p - L.p1) * (L.p2 - L.p1)) / norm(L.p2 - L.p1);
}
bool onLine(Point p, Line L) {  // 判断二维平面上点p是否在直线上
  return isZero((p - L.p1) * (L.p2 - L.p1));
}
bool onLine(Point3D p, Line3D L) {  // 判断三维平面上点p是否在直线上
  return isZero((p - L.p1) * (L.p2 - L.p1));
}
int relation(Point p, Line L) {  // 计算点和直线相对关系
  double res = (L.p2 - L.p1) * (p - L.p1);
  if (equal(res, 0)) return ONLINE;
  if (res > 0) return LEFT;
  return RIGHT;
}
bool isSameSide(Point p1, Point p2, Line L) {  // 判断p1,p2是否在直线L的同侧
  double m1 = (p1 - L.p1) * (L.p2 - L.p1);
  double m2 = (p2 - L.p1) * (L.p2 - L.p1);
  return greaterThan(m1 * m2, 0);
}
bool onLineSeg(Point p, Line L) {  // 判断平面上点p是否在线段L上
  return isZero((L.p1 - p) * (L.p2 - p))
      && lessEqual((p.x - L.p1.x) * (p.x - L.p2.x), 0)
      && lessEqual((p.y - L.p1.y) * (p.y - L.p2.y), 0);
}
bool onLineSeg(Point3D p, Line L) {  // 判断三维空间点p是否在线段L上
  return isZero((L.p1 - p) * (L.p2 - p))
      && equal(norm(p - L.p1) + norm(p - L.p2), norm(L.p2 - L.p1));
}
Point symPoint(Point p, Line L) {  // 求二维平面上点p关于L的对称点
  Point result;
  double a = L.p2.x - L.p1.x, b = L.p2.y - L.p1.y;
  double t = ((p.x - L.p1.x) * a + (p.y - L.p1.y) * b) / (a * a + b * b);
  result.x = 2 * L.p1.x + 2 * a * t - p.x;
  result.y = 2 * L.p1.y + 2 * b * t - p.y;
  return result;
}
bool coplanar(Points3D points) {  // 判断一个点集是否全部共面
  int n = points.size();
  if (n < 4) return true;
  Point3D p = (points[2] - points[0]) * (points[1] - points[0]);
  for (int i = 3; i < n; i++) {
    if (!isZero(p & points[i])) return false;
  }
  return true;
}
bool lineIntersect(Line L1, Line L2) {  // 判断二维的两条直线是否相交
  return !isZero((L1.p1 - L1.p2) * (L2.p1 - L2.p2));
}
bool lineIntersect(Line3D L1, Line3D L2) {  // 判断三维的两条直线是否相交
  Point3D p = (L1.p1 - L1.p2) * (L2.p1 - L2.p2);
  if (isZero(p)) return false;
  p = (L2.p1 - L1.p2) * (L1.p1 - L1.p2);
  return isZero(p & L2.p2);
}
bool lineSegIntersect(Line L1, Line L2) {  // 判断二维的两条线段是否相交
    return greaterEqual(max(L1.p1.x, L1.p2.x), min(L2.p1.x, L2.p2.x))
        && greaterEqual(max(L2.p1.x, L2.p2.x), min(L1.p1.x, L1.p2.x))
        && greaterEqual(max(L1.p1.y, L1.p2.y), min(L2.p1.y, L2.p2.y))
        && greaterEqual(max(L2.p1.y, L2.p2.y), min(L1.p1.y, L1.p2.y))
        && lessEqual((L2.p1 - L1.p1) * (L1.p2 - L1.p1) * (L2.p2 -  L1.p1) * (L1.p2 - L1.p1), 0)
        && lessEqual((L1.p1 - L2.p1) * (L2.p2 - L2.p1) * (L1.p2 -  L2.p1) * (L2.p2 - L2.p1), 0);
}
int calCrossPoint(Line L1, Line L2, Point& P) {  // 计算两条二维直线的交点,结果在参数P中返回
  double A1, B1, C1, A2, B2, C2;
  A1 = L1.p2.y - L1.p1.y;
  B1 = L1.p1.x - L1.p2.x;
  C1 = L1.p2.x * L1.p1.y - L1.p1.x * L1.p2.y;
  A2 = L2.p2.y - L2.p1.y;
  B2 = L2.p1.x - L2.p2.x;
  C2 = L2.p2.x * L2.p1.y - L2.p1.x * L2.p2.y;
  if (equal(A1 * B2, B1 * A2)) {
    if (equal((A1 + B1) * C2, (A2 + B2) * C1)) return COLINE;
    return PARALLEL;
  } else {
    P.x = (B2 * C1 - B1 * C2) / (A2 * B1 - A1 * B2);
    P.y = (A1 * C2 - A2 * C1) / (A2 * B1 - A1 * B2);
    return CROSS;
  }
}
Point nearestPointToLine(Point p, Line L) {  // 计算点p到直线L的最近点
  Point result;
  double a, b, t;
  a = L.p2.x - L.p1.x;
  b = L.p2.y - L.p1.y;
  t = ();

}
int main() {

  return 0;
}