sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#include "geometry/geometry.hpp"
幾何アルゴリズム詰め合わせ
Vec は std::complex<T> のエイリアスである.
Vec
std::complex<T>
できるだけ整数だけの計算も扱えるようにした
時間計算量は明示しない限り $O(1)$.
geometry.hpp
T dot(Vec a, Vec b)
T cross(Vec a, Vec b)
Vec rot(Vec a, T ang)
Vec perp(Vec a)
Vec projection(Line l, Vec p)
Vec reflection(Line l, Vec p)
int ccw(Vec a, Vec b, Vec c)
void sort_by_arg(vector<Vec> pts)
intersect.hpp
bool intersect(Segment s, Vec p)
int intersect(Polygon poly, Vec p)
bool intersect(Segment s, Segment t)
bool intersect(Polygon poly1, Polygon poly2)
int intersect(Circle c1, Circle c2)
dist.hpp
T dist(Line l, Vec p)
T dist(Segment s, Vec p)
T dist(Segment s, Segment t)
intersection.hpp
Vec intersection(Line l, Line m)
vector<Vec> intersection(Circle c, Line l)
vector<Vec> intersection(Circle c1, Circle c2)
T area_intersection(Circle c1, Circle c2)
bisector.hpp
Line bisector(Segment s)
pair<Line, Line> bisector(Line l, Line m)
triangle.hpp
Vec centroid(Vec A, Vec B, Vec C)
Vec incenter(Vec A, Vec B, Vec C)
Vec circumcenter(Vec A, Vec B, Vec C)
tangent.hpp
pair<Vec, Vec> tangent_points(Circle c, Vec p)
vector<Line> common_tangents(Circle c1, Circle c2)
polygon.hpp
T area(Polygon poly)
T is_convex(Polygon poly)
poly
Polygon convex_cut(Polygon poly, Line l)
Polygon halfplane_intersection(vector<pair<Vec, Vec>> hps)
class PolygonContainment
closest_pair.hpp
T closest_pair(vector<Vec> pts)
#pragma once #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 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); }); }