sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#include "geometry/intersect.hpp"
#pragma once #include "geometry.hpp" bool intersect(const Segment& s, const Vec& p) { Vec u = s.p1 - p, v = s.p2 - p; return eq(cross(u, v), 0) && leq(dot(u, v), 0); } // 0: outside // 1: on the border // 2: inside int intersect(const Polygon& poly, const Vec& p) { const int n = poly.size(); bool in = 0; for (int i = 0; i < n; ++i) { auto a = poly[i] - p, b = poly[(i + 1) % n] - p; if (eq(cross(a, b), 0) && (lt(dot(a, b), 0) || eq(dot(a, b), 0))) return 1; if (a.imag() > b.imag()) std::swap(a, b); if (leq(a.imag(), 0) && lt(0, b.imag()) && lt(cross(a, b), 0)) in ^= 1; } return in ? 2 : 0; } int intersect(const Segment& s, const Segment& t) { auto a = s.p1, b = s.p2; auto c = t.p1, d = t.p2; if (ccw(a, b, c) != ccw(a, b, d) && ccw(c, d, a) != ccw(c, d, b)) return 2; if (intersect(s, c) || intersect(s, d) || intersect(t, a) || intersect(t, b)) return 1; return 0; } // true if they have positive area in common or touch on the border bool intersect(const Polygon& poly1, const Polygon& poly2) { const int n = poly1.size(); const int m = poly2.size(); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (intersect(Segment(poly1[i], poly1[(i + 1) % n]), Segment(poly2[j], poly2[(j + 1) % m]))) { return true; } } } return intersect(poly1, poly2[0]) || intersect(poly2, poly1[0]); } // 0: inside // 1: inscribe // 2: intersect // 3: circumscribe // 4: outside int intersect(const Circle& c1, const Circle& c2) { T d = std::abs(c1.c - c2.c); if (lt(d, std::abs(c2.r - c1.r))) return 0; if (eq(d, std::abs(c2.r - c1.r))) return 1; if (eq(c1.r + c2.r, d)) return 3; if (lt(c1.r + c2.r, d)) return 4; return 2; }
#line 2 "geometry/geometry.hpp" #include <algorithm> #include <cassert> #include <cmath> #include <complex> #include <iostream> #include <numbers> #include <numeric> #include <vector> // note that if T is of an integer type, std::abs does not work using T = double; using Vec = std::complex<T>; std::istream& operator>>(std::istream& is, Vec& p) { T x, y; is >> x >> y; p = {x, y}; return is; } T dot(const Vec& a, const Vec& b) { return (std::conj(a) * b).real(); } T cross(const Vec& a, const Vec& b) { return (std::conj(a) * b).imag(); } constexpr T PI = std::numbers::pi_v<T>; constexpr T eps = 1e-10; inline bool eq(T a, T b) { return std::abs(a - b) <= eps; } inline bool eq(Vec a, Vec b) { return std::abs(a - b) <= eps; } inline bool lt(T a, T b) { return a < b - eps; } inline bool leq(T a, T b) { return a <= b + eps; } struct Line { Vec p1, p2; Line() = default; Line(const Vec& p1, const Vec& p2) : p1(p1), p2(p2) {} Vec dir() const { return p2 - p1; } }; struct Segment : Line { using Line::Line; }; struct Circle { Vec c; T r; Circle() = default; Circle(const Vec& c, T r) : c(c), r(r) {} }; using Polygon = std::vector<Vec>; Vec rot(const Vec& a, T ang) { return a * Vec(std::cos(ang), std::sin(ang)); } Vec perp(const Vec& a) { return Vec(-a.imag(), a.real()); } Vec projection(const Line& l, const Vec& p) { return l.p1 + dot(p - l.p1, l.dir()) * l.dir() / std::norm(l.dir()); } Vec reflection(const Line& l, const Vec& p) { return T(2) * projection(l, p) - p; } // 0: collinear // 1: counter-clockwise // -1: clockwise int ccw(const Vec& a, const Vec& b, const Vec& c) { if (eq(cross(b - a, c - a), 0)) return 0; if (lt(cross(b - a, c - a), 0)) return -1; return 1; } void sort_by_arg(std::vector<Vec>& pts) { std::ranges::sort(pts, [&](auto& p, auto& q) { if ((p.imag() < 0) != (q.imag() < 0)) return (p.imag() < 0); if (cross(p, q) == 0) { if (p == Vec(0, 0)) return !(q.imag() < 0 || (q.imag() == 0 && q.real() > 0)); if (q == Vec(0, 0)) return (p.imag() < 0 || (p.imag() == 0 && p.real() > 0)); return (p.real() > q.real()); } return (cross(p, q) > 0); }); } #line 3 "geometry/intersect.hpp" bool intersect(const Segment& s, const Vec& p) { Vec u = s.p1 - p, v = s.p2 - p; return eq(cross(u, v), 0) && leq(dot(u, v), 0); } // 0: outside // 1: on the border // 2: inside int intersect(const Polygon& poly, const Vec& p) { const int n = poly.size(); bool in = 0; for (int i = 0; i < n; ++i) { auto a = poly[i] - p, b = poly[(i + 1) % n] - p; if (eq(cross(a, b), 0) && (lt(dot(a, b), 0) || eq(dot(a, b), 0))) return 1; if (a.imag() > b.imag()) std::swap(a, b); if (leq(a.imag(), 0) && lt(0, b.imag()) && lt(cross(a, b), 0)) in ^= 1; } return in ? 2 : 0; } int intersect(const Segment& s, const Segment& t) { auto a = s.p1, b = s.p2; auto c = t.p1, d = t.p2; if (ccw(a, b, c) != ccw(a, b, d) && ccw(c, d, a) != ccw(c, d, b)) return 2; if (intersect(s, c) || intersect(s, d) || intersect(t, a) || intersect(t, b)) return 1; return 0; } // true if they have positive area in common or touch on the border bool intersect(const Polygon& poly1, const Polygon& poly2) { const int n = poly1.size(); const int m = poly2.size(); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (intersect(Segment(poly1[i], poly1[(i + 1) % n]), Segment(poly2[j], poly2[(j + 1) % m]))) { return true; } } } return intersect(poly1, poly2[0]) || intersect(poly2, poly1[0]); } // 0: inside // 1: inscribe // 2: intersect // 3: circumscribe // 4: outside int intersect(const Circle& c1, const Circle& c2) { T d = std::abs(c1.c - c2.c); if (lt(d, std::abs(c2.r - c1.r))) return 0; if (eq(d, std::abs(c2.r - c1.r))) return 1; if (eq(c1.r + c2.r, d)) return 3; if (lt(c1.r + c2.r, d)) return 4; return 2; }