library/geometry/UtilFunction.hpp

View this file on GitHub
Last update: 2025-11-24 18:49:07+09:00
Include: #include "library/geometry/UtilFunction.hpp"

Depends on

Required by

library/geometry/Judge.hpp

Verified with

test/AOJ/CGL_4_A.test.cpp

Code

#pragma once
#include "library/geometry/Base.hpp"
namespace geometry {
double cross(Vector a, Vector b) {
    // std::cerr << a <<" "<<b<<":"<<a.x*b.y-a.y*b.x<<endl;
    return a.x * b.y - a.y * b.x;
}

Point orth(Point p) { return Point(-p.y, p.x); }

Point project(Segment s, Point p) {
    Vector base = s.p2 - s.p1;
    double r = dot(p - s.p1, base) / base.norm();
    return s.p1 + base * r;
}

Point reflect(Segment s, Point p) { return p + (project(s, p) - p) * 2.0; }

Polygon convex_hull(Polygon ps) {
    int n = ps.size();
    std::ranges::sort(ps, cmp_y);
    int k = 0;
    Polygon qs(n * 2);
    for (int i = 0; i < n; i++) {
        while (k > 1 and cross(qs[k - 1] - qs[k - 2], ps[i] - qs[k - 1]) < 0)
            k--;
        qs[k++] = ps[i];
    }
    for (int i = n - 2, t = k; i >= 0; i--) {
        while (k > t and cross(qs[k - 1] - qs[k - 2], ps[i] - qs[k - 1]) < 0)
            k--;
        qs[k++] = ps[i];
    }
    qs.resize(k - 1);
    return qs;
}
} // namespace geometry

#line 2 "library/r2/XY.hpp"
template <typename T> struct XY {
    T x, y;
    XY() = default;
    XY(T x, T y) : x(x), y(y) {}
    XY(const std::pair<T, T> &xy) : x(xy.first), y(xy.second) {}

    XY operator+() const { return *this; }
    XY operator-() const { return XY(-x, -y); }

    XY &operator++() {
        x++;
        y++;
        return *this;
    }
    XY &operator--() {
        x--;
        y--;
        return *this;
    }
    XY &operator++(int) {
        XY a = *this;
        ++*this;
        return a;
    }
    XY &operator--(int) {
        XY a = *this;
        --*this;
        return a;
    }

    XY &operator+=(const XY &v) {
        x += v.x;
        y += v.y;
        return *this;
    }
    XY &operator-=(const XY &v) {
        x -= v.x;
        y -= v.y;
        return *this;
    }
    XY &operator*=(const T &a) {
        x *= a;
        y *= a;
        return *this;
    }
    XY &operator/=(const T &a) {
        x /= a;
        y /= a;
        return *this;
    }

    friend XY operator+(const XY &u, const XY &v) { return XY(u) += v; }
    friend XY operator-(const XY &u, const XY &v) { return XY(u) -= v; }
    friend XY operator*(const XY &u, const T &a) { return XY(u) *= a; }
    friend XY operator*(const T &a, const XY &u) { return XY(u) *= a; }
    friend XY operator/(const XY &u, const T &a) { return XY(u) /= a; }

    bool operator<(const XY &v) const { return x != v.x ? x < v.x : y < v.y; }
    bool operator>(const XY &v) const { return x != v.x ? x > v.x : y > v.y; }
    bool operator==(const XY &v) const { return x == v.x and y == v.y; }
    bool operator<=(const XY &v) const { return !(*this > v); }
    bool operator>=(const XY &v) const { return !(*this < v); }
    bool operator!=(const XY &v) const { return !(*this == v); }

    double arg() const { return atan2(y, x); }

    // [0,2pi) で θ(u)<θ(v) の時 true
    // (0,0) は 2pi に相当
    // static bool angle_cmp(const XY&u,const XY&v){
    //  using U=conditional_t< is_same_v<T,int>,long long,T>;
    //  if(u==XY(0,0))return false;
    //  if(v==XY(0,0))return true;
    //  if(u.y==0){
    //    if(u.x>0)return true;
    //    if(v.y==0)return v.x<0;
    //    return v.y<0;
    //  }
    //  if(u.y>0){
    //    if(v.y==0)return v.x<0;
    //    if(v.y<0)return true;
    //    return U(v.x)*u.y <= U(u.x)*v.y;
    //  }
    //  if(v.y>=0)return false;
    //  return U(v.x)*u.y <= U(u.x)*v.y;
    //}

    friend T dot(const XY &u, const XY &v) { return u.x * v.x + u.y * v.y; }
    T norm() { return dot(*this, *this); }
    T abs() { return sqrt(norm()); }

    friend std::istream &operator>>(std::istream &is, XY &v) {
        is >> v.x >> v.y;
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const XY &v) {
        os << v.x << " " << v.y;
        return os;
    }

    static XY direction(const char &c) {
        if (c == 'R')
            return {1, 0};
        if (c == 'L')
            return {-1, 0};
        if (c == 'U')
            return {0, -1};
        if (c == 'D')
            return {0, 1};
        return {0, 0};
    }
};
#line 3 "library/geometry/Base.hpp"
namespace geometry {
constexpr double EPS = 1e-10, PI = acos(-1);

bool is_equal(double a, double b) { return abs(a - b) < EPS; }

using Point = XY<double>;
bool cmp_y(const Point &p1, const Point &p2) {
    return p1.y != p2.y ? p1.y < p2.y : p1.x < p2.x;
}

using Vector = Point;
using Polygon = std::vector<Point>;

std::istream &operator>>(std::istream &is, Polygon &p) {
    for (Point &c : p)
        is >> c;
    return is;
}

struct Segment {
    Point p1, p2;
    Segment() {}
    Segment(Point p1, Point p2) : p1(p1), p2(p2) {}
    friend std::istream &operator>>(std::istream &is, Segment &s) {
        is >> s.p1 >> s.p2;
        return is;
    }
    double arg() const { return (p2 - p1).arg(); }
};
using Line = Segment;

struct Circle {
    Point c;
    double r;
    Circle() {}
    Circle(Point c, double r) : c(c), r(r) {}
    friend std::istream &operator>>(std::istream &is, Circle &c) {
        is >> c.c >> c.r;
        return is;
    }
};
} // namespace geometry
#line 3 "library/geometry/UtilFunction.hpp"
namespace geometry {
double cross(Vector a, Vector b) {
    // std::cerr << a <<" "<<b<<":"<<a.x*b.y-a.y*b.x<<endl;
    return a.x * b.y - a.y * b.x;
}

Point orth(Point p) { return Point(-p.y, p.x); }

Point project(Segment s, Point p) {
    Vector base = s.p2 - s.p1;
    double r = dot(p - s.p1, base) / base.norm();
    return s.p1 + base * r;
}

Point reflect(Segment s, Point p) { return p + (project(s, p) - p) * 2.0; }

Polygon convex_hull(Polygon ps) {
    int n = ps.size();
    std::ranges::sort(ps, cmp_y);
    int k = 0;
    Polygon qs(n * 2);
    for (int i = 0; i < n; i++) {
        while (k > 1 and cross(qs[k - 1] - qs[k - 2], ps[i] - qs[k - 1]) < 0)
            k--;
        qs[k++] = ps[i];
    }
    for (int i = n - 2, t = k; i >= 0; i--) {
        while (k > t and cross(qs[k - 1] - qs[k - 2], ps[i] - qs[k - 1]) < 0)
            k--;
        qs[k++] = ps[i];
    }
    qs.resize(k - 1);
    return qs;
}
} // namespace geometry