library/r2/Projection.hpp

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

Depends on

Verified with

Code

#pragma once
#include "library/r2/XY.hpp"
#include "library/util/Compress.hpp"
template <typename T> class Projection {
    using r2 = XY<T>;
    Compress<r2> C;

  public:
    Projection(const std::vector<r2> &v) : C(v) {}
    int size() { return C.size(); }
    int id(r2 xy) { return C[xy]; }
    int id(int x, int y) { return C[r2(x, y)]; }
    r2 r(int id) { return C.r(id); }
    //[l,r) を返す
    std::pair<int, int> interval(const T &l, const T &r) {
        if (C.max().x < l or r <= C.min().x)
            return std::make_pair(0, 0);
        T mn = std::numeric_limits<T>::min();
        int L = C.geq(r2(l, mn));
        int R = C.geq(r2(r, mn));
        return std::make_pair(L, R);
    }
};

#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 2 "library/util/Compress.hpp"
template <typename T, bool Sentinel = false> class Compress {
    std::vector<T> v;
    bool prepared;

  public:
    Compress() : prepared(false) {
        if constexpr (Sentinel) {
            static_assert(std::numeric_limits<T>::is_specialized,
                          "cannot use Sentinel");
            v = {std::numeric_limits<T>::min(), std::numeric_limits<T>::max()};
        }
    }
    Compress(const std::vector<T> &w) : v(w), prepared(false) {
        if constexpr (Sentinel) {
            static_assert(std::numeric_limits<T>::is_specialized,
                          "cannot use Sentinel");
            v.push_back(std::numeric_limits<T>::min());
            v.push_back(std::numeric_limits<T>::max());
        }
        build();
    }

    void add(T a) {
        assert(!prepared);
        v.push_back(a);
    }
    void build() {
        assert(!prepared);
        prepared = true;
        std::ranges::sort(v);
        auto result = std::ranges::unique(v);
        v.erase(result.begin(), result.end());
    }

    bool is_prepared() const { return prepared; }

    int operator[](const T &a) const {
        assert(prepared);
        auto it = std::ranges::lower_bound(v, a);
        assert(*it == a);
        return std::distance(v.begin(), it);
    }
    int geq(const T &a) const {
        assert(prepared);
        auto it = std::ranges::lower_bound(v, a);
        return std::distance(v.begin(), it);
    }
    int gt(const T &a) const {
        assert(prepared);
        auto it = std::ranges::upper_bound(v, a);
        return std::distance(v.begin(), it);
    }
    int leq(const T &a) const {
        assert(prepared);
        auto it = --std::ranges::upper_bound(v, a);
        return std::distance(v.begin(), it);
    }
    int lt(const T &a) const {
        assert(prepared);
        auto it = --std::ranges::lower_bound(v, a);
        return std::distance(v.begin(), it);
    }
    T r(int id) const {
        assert(prepared);
        return v[id];
    }
    bool exist(const T &a) const {
        assert(prepared);
        return (*std::ranges::lower_bound(v, a)) == a;
    }
    int size() const { return v.size(); }
    T max() const { return v.back(); }
    T min() const { return v[0]; }

    friend std::ostream &operator<<(std::ostream &os, const Compress &C) {
        for (int i = 0; i < C.v.size(); i++)
            os << C.v[i] << ":" << i << " ";
        return os;
    }
};
#line 4 "library/r2/Projection.hpp"
template <typename T> class Projection {
    using r2 = XY<T>;
    Compress<r2> C;

  public:
    Projection(const std::vector<r2> &v) : C(v) {}
    int size() { return C.size(); }
    int id(r2 xy) { return C[xy]; }
    int id(int x, int y) { return C[r2(x, y)]; }
    r2 r(int id) { return C.r(id); }
    //[l,r) を返す
    std::pair<int, int> interval(const T &l, const T &r) {
        if (C.max().x < l or r <= C.min().x)
            return std::make_pair(0, 0);
        T mn = std::numeric_limits<T>::min();
        int L = C.geq(r2(l, mn));
        int R = C.geq(r2(r, mn));
        return std::make_pair(L, R);
    }
};