计算几何模板整理

新一轮的模板整理采用分模块的方式，同时只保留重要内容，删去简短能够在赛场直接写出来并且不是每个题都要用的东西。

upd：圆相关的很多东西我都是现推的，所以该部分内容不完整。其他东西都是验证过正确性的。由于 SCOI2024 打完了，所以本篇不再维护。

点和向量

const double PI = acos(-1);
const double eps = 1e-8;
const double Infdb = 1e18;

inline int dcmp(double x) {return x < -eps ? -1 : x > eps;}
struct Point {
  double x, y;
  Point(double x = 0, double y = 0) : x(x), y(y) {}
  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 p) {return Point(x * p, y * p);}
  double operator*(Point b) {return x * b.x + y * b.y;}
  double operator^(Point b) {return x * b.y - y * b.x;}
  double len() {return sqrt(x * x + y * y);}
  bool operator<(Point b) const {
    return !dcmp(x - b.x) ? dcmp(y - b.y) < 0 : dcmp(x - b.x) < 0;
  }
  bool operator==(Point b) {return !dcmp(x - b.x) && !dcmp(y - b.y);}
  Point rot(double p) {
    return Point(x * cos(p) - y * sin(p), x * sin(p) + y * cos(p));
  }
};
double ang(Point a, Point b) {
  return acos((a * b) / a.len() / b.len());
}

直线相关

bool onSeg(Point p, Point a, Point b) {
  return !dcmp((p - a) ^ (p - b)) && dcmp((p - a) * (p - b)) <= 0;
}
bool onLine(Point p, Point a, Point b) {
  return !dcmp((p - a) ^ (p - b));
}
double toLine(Point p, Point a, Point b) {
  Point v = b - a;
  return fabs(v ^ (p - a)) / v.len();
}
Point foot(Point p, Point a, Point b) {
  Point v = b - a;
  return a + v * ((v * (p - a)) / (v * v));
}
int side(Point p, Point a, Point b) {
  return dcmp((p - a) ^ (b - a));
}
double toSeg(Point p, Point a, Point b) {
  if (a == b) return (p - a).len();
  Point x = p - a, y = p - b, z = b - a;
  if (dcmp(x * z) < 0) return x.len();
  if (dcmp(y * z) > 0) return y.len();
  return toLine(p, a, b);
}
Point inter(Point a, Point b, Point c, Point d) {
  Point x = b - a, y = d - c, z = a - c;
  return a + x * ((y ^ z) / (x ^ y));
}
struct Line {
  Point a, b;
  double k;
  Line() {}
  Line(Point a, Point b) : a(a), b(b) {
    k = atan2(b.y - a.y, b.x - a.x);
  }
  bool operator<(Line rhs) const {
    if (dcmp(k - rhs.k)) return dcmp(k - rhs.k) < 0;
    return side(rhs.a, a, b) == 1;
  }
};
Point inter(Line p, Line q) {
  return inter(p.a, p.b, q.a, q.b);
}

多边形相关

typedef vector<Point> vPoint;
vPoint convexHull(vPoint A) {
  int n = A.size(), m = 0;
  if (n <= 1) return A;
  sort(A.begin(), A.end());
  vPoint B(2 * n);
  for (int i = 0; i < n; B[m++] = A[i++])
    while (m > 1 && dcmp((A[i] - B[m - 2]) ^ (B[m - 1] - B[m - 2])) >= 0) --m;
  for (int i = n - 2, t = m; ~i; B[m++] = A[i--])
    while (m > t && dcmp((A[i] - B[m - 2]) ^ (B[m - 1] - B[m - 2])) >= 0) --m;
  B.resize(m - 1);
  return B;
}
int inPoly(vPoint A, Point p) {
  int n = A.size(), wn = 0;
  for (int i = 0; i < n; ++i) {
    Point a = A[i], b = A[(i + 1) % n];
    if (onSeg(p, a, b)) return 2;
    int k = side(b, a, p);
    int d1 = dcmp(a.y - p.y), d2 = dcmp(b.y - p.y);
    if (k > 0 && d1 <= 0 && d2 > 0) wn++;
    if (k < 0 && d2 <= 0 && d1 > 0) wn--;
  }
  return wn != 0;
}
int inConvexPoly(const vPoint &A, Point p) {
  int n = A.size();
  if (side(p, A[0], A[1]) == 1 || side(A[n - 1], A[0], p) == 1) return 0;
  if (onSeg(p, A[0], A[1]) || onSeg(p, A[0], A[n - 1])) return 2;
  int l = 1, r = n - 2;
  while (l < r) {
    int mid = (l + r + 1) >> 1;
    if (side(A[mid], A[0], p) == 1) l = mid;
    else r = mid - 1;
  }
  if (side(p, A[l], A[l + 1]) == 1) return 0;
  if (onSeg(p, A[l], A[l + 1])) return 2;
  return 1;
}

圆相关

struct Circle {
  Point p;
  double r;
  Circle(Point p, double r = 0) : p(p), r(r) {}
  Point get(double ang) {
    return Point(p.x + cos(ang) * r, p.y + sin(ang) * r);
  }
};
int side(Circle c, Point a) {
  return dcmp((a - c.p).len() - c.r);
}
int side(Circle a, Circle b) {
  double d = (b.p - a.p).len();
  int f = dcmp(d - (a.r - b.r));
  if (f == 0 && !dcmp(a.r - b.r)) f = -2;
  if (f > 0) f = 2 + dcmp(d - (a.r + b.r));
  return f;
}
int inter(Circle c, Point a, Point b, vPoint &res) {
  double d = toLine(c.p, a, b);
  int f = dcmp(d - c.r);
  if (f < -1) return 0;
  else if (!f) {
    res.push_back(foot(c.p, a, b));
    return 1;
  } else {
    Point p = foot(c.p, a, b), v = b - a;
    double l = sqrt(c.r * c.r - d * d);
    res.push_back(p + v * (l / v.len()));
    res.push_back(p - v * (l / v.len()));
    return 2;
  }
}
int inter(Circle a, Circle b, vPoint &res) {
  if (a.r < b.r) swap(a, b);
  int k = side(a, b);
  Point v = b.p - a.p;
  double d = v.len(), base = atan2(v.y, v.x);
  if (k == 0 || k == 2) res.push_back(a.get(base));
  if (k == 1) {
    double ag = acos((a.r * a.r + d * d - b.r * b.r) / (a.r * d));
    res.push_back(a.get(base + ag));
    res.push_back(a.get(base - ag));
  }
  return k;
}

半平面交

vPoint halfCut(vector<Line> L) {
  int n = 0;
  sort(L.begin(), L.end());
  for (int i = 0; i < L.size(); ++i)
    if (!i || dcmp(L[i].k - L[i - 1].k)) L[n++] = L[i];
  int h = 1, t = 0;
  vector<Line> Q(n + 1);
  for (int i = 0; i < n; ++i) {
    while (h < t && side(inter(Q[t - 1], Q[t]), L[i].a, L[i].b) == 1) --t;
    while (h < t && side(inter(Q[h + 1], Q[h]), L[i].a, L[i].b) == 1) ++h;
    if (h <= t && !dcmp(fabs(Q[t].k - L[i].k) - PI) && side(Q[t].a, L[i].a, L[i].b) >= 0)
      return vPoint();
    Q[++t] = L[i];
  }
  while (h < t && side(inter(Q[t - 1], Q[t]), Q[h].a, Q[h].b) == 1) --t;
  while (h < t && side(inter(Q[h + 1], Q[h]), Q[t].a, Q[t].b) == 1) ++h;
  vPoint A;
  for (int i = h; i <= t; ++i) {
    int j = i == t ? h : i + 1;
    A.push_back(inter(Q[i], Q[j]));
  }
  return A;
}

动态凸包

下凸壳 $op = 1$，上凸壳 $op = -1$。

模板题 CF70D

struct ConvexHull {
  int op;
  set<Point> s;
  bool in(Point p) {
    auto it = s.lower_bound(Point(p.x, -Infdb));
    if (it == s.end()) return 0;
    if (!dcmp(it->x - p.x)) return op * dcmp(p.y - it->y) >= 0;
    if (it == s.begin()) return 0;
    Point b = *it, a = *--it;
    return op * ((b - a) ^ (p - a)) >= 0;
  }
  bool judge(auto it) {
    if (next(it) == s.end() || it == s.begin()) return 0;
    Point p = *it, a = *prev(it), b = *next(it);
    return op * dcmp((b - a) ^ (p - a)) >= 0;
  }
  void ins(Point p) {
    if (in(p)) return;
    auto it = s.lower_bound(Point(p.x, -Infdb));
    if (it != s.end() && !dcmp(it->x - p.x)) s.erase(it);
    s.insert(p), it = s.find(p);
    auto cur = next(it);
    while (cur != s.end() && judge(cur)) cur = s.erase(cur);
    if (it != s.begin()) {
      cur = prev(it);
      while (judge(cur)) s.erase(cur--);
    }
  }
} up, down;