This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub
#include "C++/core/mypair.hpp"
#pragma once #include <cassert> #include <utility> #include <tuple> #include <cmath> #include <numeric> #include "C++/core/constance.hpp" #include "C++/core/myvector.hpp" namespace pairs { template <class T, class U> using P = std::pair<T, U>; template <class T> using PP = P<T,T>; using pi = PP<ll>; using pd = PP<ld>; using pc = PP<char>; using ps = PP<std::string>; template <class T> constexpr PP<T> operator+(const PP<T>& a, const PP<T>& b) noexcept { return {a.first + b.first, a.second + b.second}; } template <class T> constexpr PP<T> operator-(const PP<T>& a, const PP<T>& b) noexcept { return {a.first - b.first, a.second - b.second}; } template <class T> constexpr PP<T> operator-(const PP<T>& a) noexcept { return {-a.first, -a.second}; } template <class T, class U> constexpr PP<T> operator*(const PP<T>& a, const U& b) noexcept { return {a.first * b, a.second * b}; } template <class T, class U> constexpr PP<T> operator/(const PP<T>& a, const U& b) noexcept { return {a.first / b, a.second / b}; } template <class T> constexpr PP<T>& operator+=(PP<T>& a, const PP<T>& b) noexcept { return a = a + b; } template <class T> constexpr PP<T>& operator-=(PP<T>& a, const PP<T>& b) noexcept { return a = a - b; } template <class T, class U> constexpr PP<T>& operator*=(PP<T>& a, const U& b) noexcept { return a = a * b; } template <class T, class U> PP<T>& operator/=(PP<T>& a, const U& b) noexcept { return a = a / b; } template <class T> constexpr bool operator==(const PP<T> &p, const PP<T> &q) noexcept { return p.first==q.first && p.second==q.second; } template <class T> constexpr bool operator!=(const PP<T> &p, const PP<T> &q) noexcept { return !(p==q); } template <class T> constexpr bool operator<(const PP<T> &p, const PP<T> &q) noexcept { if(p.first==q.first) return p.second<q.second; return p.first<q.first; } template <class T> constexpr bool operator<=(const PP<T> &p, const PP<T> &q) noexcept { if(p.first==q.first) return p.second<=q.second; return p.first<q.first; } template <class T> constexpr bool operator>(const PP<T> &p, const PP<T> &q) noexcept { if(p.first==q.first) return p.second>q.second; return p.first>q.first; } template <class T> constexpr bool operator>=(const PP<T> &p, const PP<T> &q) noexcept { if(p.first==q.first) return p.second>=q.second; return p.first>q.first; } template <class T, class U> constexpr bool operator==(const P<T,U> &p, const P<T,U> &q) noexcept { return p.first==q.first && p.second==q.second; } template <class T, class U> constexpr bool operator!=(const P<T,U> &p, const P<T,U> &q) noexcept { return !(p==q); } template <class T, class U> constexpr bool operator<(const P<T,U> &p, const P<T,U> &q) noexcept { if(p.first==q.first) return p.second<q.second; return p.first<q.first; } template <class T, class U> constexpr bool operator<=(const P<T,U> &p, const P<T,U> &q) noexcept { if(p.first==q.first) return p.second<=q.second; return p.first<q.first; } template <class T, class U> constexpr bool operator>(const P<T,U> &p, const P<T,U> &q) noexcept { if(p.first==q.first) return p.second>q.second; return p.first>q.first; } template <class T, class U> constexpr bool operator>=(const P<T,U> &p, const P<T,U> &q) noexcept { if(p.first==q.first) return p.second>=q.second; return p.first>q.first; } template <class T> inline PP<T> rotate(const PP<T>& a){ return {-a.second, a.first}; } // 90 degree ccw template <class T> inline pd rotate(const PP<T>& a, const int ang) { assert(0<=ang && ang<360); const ld rad=PI*ang/180; return {a.first*std::cos(rad)-a.second*std::sin(rad), a.first*std::sin(rad)+a.second*std::cos(rad)}; } template <class T> inline T dot(const PP<T>& a, const PP<T>& b){ return a.first * b.first + a.second * b.second; } template <class T> inline T cross(const PP<T>& a, const PP<T>& b){ return dot(rotate(a), b); } template <class T> inline T square(const PP<T>& a){ return dot(a, a); } template <class T> inline ld grad(const PP<T>& a){ assert(a.first); return 1.0L * a.second / a.first; } template <class T> inline ld abs(const PP<T>& a){ return std::hypotl(a.first, a.second); } template <class T> inline T lcm(const PP<T>& a){ return std::lcm(a.first, a.second); } template <class T> inline T gcd(const PP<T>& a){ return std::gcd(a.first, a.second); } template <class T> inline PP<T> extgcd(const PP<T> &p) { T x=1,y=0,t1=0,t2=0,t3=1,a,b; std::tie(a,b)=p; while(b) { t1=a/b,a-=t1*b; std::swap(a,b); x-=t1*t2; std::swap(x,t2); y-=t1*t3; std::swap(y,t3); } return {x,y}; } template <class T> inline PP<T> normalize(PP<T> a) { if(a == PP<T>{}) return a; a /= gcd(a); if(a < PP<T>{}) a = -a; return a; } template <class T, class U> inline P<U,T> swap(const P<T,U> &p){ P<U,T> ret={p.second,p.first}; return ret; } template <class T, class U> inline vectors::V<P<U,T>> swap(const vectors::V<P<T,U>> &vp) { vectors::V<P<U,T>> ret; for(const auto &el: vp) ret.emplace_back(swap(el)); return ret; } template <class T, class U> inline vectors::V<T> first(const vectors::V<P<T,U>> &vp) { vectors::V<T> res; for(const auto &el: vp) res.emplace_back(el.first); return res; } template <class T, class U> inline vectors::V<U> second(const vectors::V<P<T,U>> &vp) { vectors::V<U> res; for(const auto &el: vp) res.emplace_back(el.second); return res; } } // pairs
#line 2 "C++/core/mypair.hpp" #include <cassert> #include <utility> #include <tuple> #include <cmath> #include <numeric> #line 2 "C++/core/constance.hpp" #include <limits> #ifndef TEMPLATE using ll = long long; using ld = long double; #endif template <class T> using L = std::numeric_limits<T>; constexpr int dx[] = {0, 0, 0, -1, 1, -1, -1, 1, 1}; constexpr int dy[] = {0, -1, 1, 0, 0, -1, 1, -1, 1}; constexpr int MOD = 0x3b800001; constexpr int M0D = 1e9 + 7; constexpr int INF = 1 << 30; constexpr ll LINF = (1LL << 61) - 1; constexpr ld DINF = L<ld>::infinity(); template <class T> constexpr T LIM = L<T>::max(); #if __cplusplus >= 202100L #include <numbers> constexpr ld PI = std::numbers::pi; constexpr ld E = std::numbers::e; #else #line 23 "C++/core/constance.hpp" const ld PI = std::acos(-1); const ld E = 2.718281828459045; #endif /** * @brief 定数 */ #line 2 "C++/core/myvector.hpp" #include <vector> #ifndef TEMPLATE typedef long long ll; typedef unsigned long long ul; typedef long double ld; #endif namespace vectors { template <class T> using V = std::vector<T>; using vi = V<ll>; using vu = V<ul>; using vd = V<ld>; using vc = V<char>; using vs = V<std::string>; using vb = V<bool>; using wi = V<vi>; using wu = V<vu>; using wd = V<vd>; using wc = V<vc>; using ws = V<vs>; using wb = V<vb>; template <class T, class U> inline V<U> ndiv(T&& n, U&& v) noexcept { return V<U>(std::forward<T>(n), std::forward<U>(v)); } template <class T, class... Ts> inline decltype(auto) ndiv(T&& n, Ts&&... v) noexcept { return V<decltype(ndiv(std::forward<Ts>(v)...))>(std::forward<T>(n), ndiv(std::forward<Ts>(v)...)); } template <class T> constexpr V<T>& operator++(V<T>& v) noexcept { for(auto &el: v) el++; return v; } template <class T> constexpr V<T>& operator--(V<T>& v) noexcept { for(auto &el: v) el--; return v; } template <class T, class U> constexpr V<T>& operator+=(V<T>& v, const U x) noexcept { for(auto &el: v) el+=x; return v; } template <class T, class U> constexpr V<T>& operator-=(V<T>& v, const U x) noexcept { for(auto &el: v) el-=x; return v; } template <class T, class U> constexpr V<T>& operator*=(V<T>& v, const U x) noexcept { for(auto &el: v) el*=x; return v; } template <class T, class U> constexpr V<T>& operator/=(V<T>& v, const U x) noexcept { for(auto &el: v) el/=x; return v; } template <class T, class U> constexpr V<T>& operator%=(V<T>& v, const U x) noexcept { for(auto &el: v) el%=x; return v; } template <class T, class U> constexpr V<T> operator+(const V<T>& v, const U x) noexcept { V<T> res = v; res+=x; return res; } template <class T, class U> constexpr V<T> operator-(const V<T>& v, const U x) noexcept { V<T> res = v; res-=x; return res; } template <class T, class U> constexpr V<T> operator*(const V<T>& v, const U x) noexcept { V<T> res = v; res*=x; return res; } template <class T, class U> constexpr V<T> operator/(const V<T>& v, const U x) noexcept { V<T> res = v; res/=x; return res; } template <class T, class U> constexpr V<T> operator%(const V<T>& v, const U x) noexcept { V<T> res = v; res%=x; return res; } } // vectors #line 10 "C++/core/mypair.hpp" namespace pairs { template <class T, class U> using P = std::pair<T, U>; template <class T> using PP = P<T,T>; using pi = PP<ll>; using pd = PP<ld>; using pc = PP<char>; using ps = PP<std::string>; template <class T> constexpr PP<T> operator+(const PP<T>& a, const PP<T>& b) noexcept { return {a.first + b.first, a.second + b.second}; } template <class T> constexpr PP<T> operator-(const PP<T>& a, const PP<T>& b) noexcept { return {a.first - b.first, a.second - b.second}; } template <class T> constexpr PP<T> operator-(const PP<T>& a) noexcept { return {-a.first, -a.second}; } template <class T, class U> constexpr PP<T> operator*(const PP<T>& a, const U& b) noexcept { return {a.first * b, a.second * b}; } template <class T, class U> constexpr PP<T> operator/(const PP<T>& a, const U& b) noexcept { return {a.first / b, a.second / b}; } template <class T> constexpr PP<T>& operator+=(PP<T>& a, const PP<T>& b) noexcept { return a = a + b; } template <class T> constexpr PP<T>& operator-=(PP<T>& a, const PP<T>& b) noexcept { return a = a - b; } template <class T, class U> constexpr PP<T>& operator*=(PP<T>& a, const U& b) noexcept { return a = a * b; } template <class T, class U> PP<T>& operator/=(PP<T>& a, const U& b) noexcept { return a = a / b; } template <class T> constexpr bool operator==(const PP<T> &p, const PP<T> &q) noexcept { return p.first==q.first && p.second==q.second; } template <class T> constexpr bool operator!=(const PP<T> &p, const PP<T> &q) noexcept { return !(p==q); } template <class T> constexpr bool operator<(const PP<T> &p, const PP<T> &q) noexcept { if(p.first==q.first) return p.second<q.second; return p.first<q.first; } template <class T> constexpr bool operator<=(const PP<T> &p, const PP<T> &q) noexcept { if(p.first==q.first) return p.second<=q.second; return p.first<q.first; } template <class T> constexpr bool operator>(const PP<T> &p, const PP<T> &q) noexcept { if(p.first==q.first) return p.second>q.second; return p.first>q.first; } template <class T> constexpr bool operator>=(const PP<T> &p, const PP<T> &q) noexcept { if(p.first==q.first) return p.second>=q.second; return p.first>q.first; } template <class T, class U> constexpr bool operator==(const P<T,U> &p, const P<T,U> &q) noexcept { return p.first==q.first && p.second==q.second; } template <class T, class U> constexpr bool operator!=(const P<T,U> &p, const P<T,U> &q) noexcept { return !(p==q); } template <class T, class U> constexpr bool operator<(const P<T,U> &p, const P<T,U> &q) noexcept { if(p.first==q.first) return p.second<q.second; return p.first<q.first; } template <class T, class U> constexpr bool operator<=(const P<T,U> &p, const P<T,U> &q) noexcept { if(p.first==q.first) return p.second<=q.second; return p.first<q.first; } template <class T, class U> constexpr bool operator>(const P<T,U> &p, const P<T,U> &q) noexcept { if(p.first==q.first) return p.second>q.second; return p.first>q.first; } template <class T, class U> constexpr bool operator>=(const P<T,U> &p, const P<T,U> &q) noexcept { if(p.first==q.first) return p.second>=q.second; return p.first>q.first; } template <class T> inline PP<T> rotate(const PP<T>& a){ return {-a.second, a.first}; } // 90 degree ccw template <class T> inline pd rotate(const PP<T>& a, const int ang) { assert(0<=ang && ang<360); const ld rad=PI*ang/180; return {a.first*std::cos(rad)-a.second*std::sin(rad), a.first*std::sin(rad)+a.second*std::cos(rad)}; } template <class T> inline T dot(const PP<T>& a, const PP<T>& b){ return a.first * b.first + a.second * b.second; } template <class T> inline T cross(const PP<T>& a, const PP<T>& b){ return dot(rotate(a), b); } template <class T> inline T square(const PP<T>& a){ return dot(a, a); } template <class T> inline ld grad(const PP<T>& a){ assert(a.first); return 1.0L * a.second / a.first; } template <class T> inline ld abs(const PP<T>& a){ return std::hypotl(a.first, a.second); } template <class T> inline T lcm(const PP<T>& a){ return std::lcm(a.first, a.second); } template <class T> inline T gcd(const PP<T>& a){ return std::gcd(a.first, a.second); } template <class T> inline PP<T> extgcd(const PP<T> &p) { T x=1,y=0,t1=0,t2=0,t3=1,a,b; std::tie(a,b)=p; while(b) { t1=a/b,a-=t1*b; std::swap(a,b); x-=t1*t2; std::swap(x,t2); y-=t1*t3; std::swap(y,t3); } return {x,y}; } template <class T> inline PP<T> normalize(PP<T> a) { if(a == PP<T>{}) return a; a /= gcd(a); if(a < PP<T>{}) a = -a; return a; } template <class T, class U> inline P<U,T> swap(const P<T,U> &p){ P<U,T> ret={p.second,p.first}; return ret; } template <class T, class U> inline vectors::V<P<U,T>> swap(const vectors::V<P<T,U>> &vp) { vectors::V<P<U,T>> ret; for(const auto &el: vp) ret.emplace_back(swap(el)); return ret; } template <class T, class U> inline vectors::V<T> first(const vectors::V<P<T,U>> &vp) { vectors::V<T> res; for(const auto &el: vp) res.emplace_back(el.first); return res; } template <class T, class U> inline vectors::V<U> second(const vectors::V<P<T,U>> &vp) { vectors::V<U> res; for(const auto &el: vp) res.emplace_back(el.second); return res; } } // pairs