This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub suisen-cp/cp-library-cpp
#include "library/integral_geom/sort_points_by_argument.hpp"
#ifndef SUISEN_SORT_POINTS_BY_ARGUMENT #define SUISEN_SORT_POINTS_BY_ARGUMENT #include <algorithm> #include <vector> #include "library/integral_geom/point.hpp" namespace suisen::integral_geometry { /** * 1. (x < 0, y = 0) -> pi * 2. (x = 0, y = 0) -> 0 * 3. points with same argument -> arbitrary order */ template <typename PointType, typename MultipliedType = long long> bool compare_by_atan2(const PointType &p, const PointType &q) { const auto &[x1, y1] = p; const auto &[x2, y2] = q; if ((y1 < 0) xor (y2 < 0)) return y1 < y2; if ((x1 < 0) xor (x2 < 0)) return (y1 >= 0) xor (x1 < x2); if (x1 == 0 and y1 == 0) return true; if (x2 == 0 and y2 == 0) return false; return (MultipliedType(y1) * x2 < MultipliedType(y2) * x1); } template <typename PointType, typename MultipliedType = long long> void sort_points_by_argument(std::vector<PointType> &points) { std::sort(points.begin(), points.end(), compare_by_atan2<PointType, MultipliedType>); } } // namespace suisen::integral_geometry #endif // SUISEN_SORT_POINTS_BY_ARGUMENT
#line 1 "library/integral_geom/sort_points_by_argument.hpp" #include <algorithm> #include <vector> #line 1 "library/integral_geom/point.hpp" #include <cassert> #include <iostream> #include <utility> #ifndef COORDINATE_TYPE #define COORDINATE_TYPE long long #endif // COORDINATE_TYPE #ifndef MULTIPLIED_TYPE #define MULTIPLIED_TYPE long long #endif // MULTIPLIED_TYPE namespace suisen::integral_geometry { using coordinate_t = COORDINATE_TYPE; using multiplied_t = MULTIPLIED_TYPE; struct Point { coordinate_t x, y; constexpr Point(coordinate_t x = 0, coordinate_t y = 0) : x(x), y(y) {} template <typename T = coordinate_t, typename U = coordinate_t> operator std::pair<T, U>() const { return std::pair<T, U> { T{ x }, U{ y } }; } template <typename T, typename U> Point& operator=(const std::pair<T, U> &p) { x = p.first, y = p.second; return *this; } friend Point operator+(const Point& p) { return p; } friend Point operator-(const Point& p) { return { -p.x, -p.y }; } friend Point operator+(const Point& lhs, const Point& rhs) { return { lhs.x + rhs.x, lhs.y + rhs.y }; } friend Point operator-(const Point& lhs, const Point& rhs) { return { lhs.x - rhs.x, lhs.y - rhs.y }; } friend Point operator*(const Point& lhs, const Point& rhs) { return { lhs.x * rhs.x - lhs.y * rhs.y, lhs.x * rhs.y + lhs.y * rhs.x }; } friend Point& operator+=(Point& lhs, const Point& rhs) { lhs.x += rhs.x, lhs.y += rhs.y; return lhs; } friend Point& operator-=(Point& lhs, const Point& rhs) { lhs.x -= rhs.x, lhs.y -= rhs.y; return lhs; } friend Point& operator*=(Point& lhs, const Point& rhs) { return lhs = lhs * rhs; } friend Point operator+(const Point& p, coordinate_t real) { return { p.x + real, p.y }; } friend Point operator-(const Point& p, coordinate_t real) { return { p.x - real, p.y }; } friend Point operator*(const Point& p, coordinate_t real) { return { p.x * real, p.y * real }; } friend Point operator/(const Point& p, coordinate_t real) { return { p.x / real, p.y / real }; } friend Point operator+=(Point& p, coordinate_t real) { p.x += real; return p; } friend Point operator-=(Point& p, coordinate_t real) { p.x -= real; return p; } friend Point operator*=(Point& p, coordinate_t real) { p.x *= real, p.y *= real; return p; } friend Point operator/=(Point& p, coordinate_t real) { p.x /= real, p.y /= real; return p; } friend Point operator+(coordinate_t real, const Point& p) { return { real + p.x, p.y }; } friend Point operator-(coordinate_t real, const Point& p) { return { real - p.x, -p.y }; } friend Point operator*(coordinate_t real, const Point& p) { return { real * p.x, real * p.y }; } friend bool operator==(const Point& lhs, const Point& rhs) { return lhs.x == rhs.x and lhs.y == rhs.y; } friend bool operator!=(const Point& lhs, const Point& rhs) { return not (lhs == rhs); } friend std::istream& operator>>(std::istream& in, Point& p) { return in >> p.x >> p.y; } friend std::ostream& operator<<(std::ostream& out, const Point& p) { return out << p.x << ' ' << p.y; } template <std::size_t I> coordinate_t get() const { if constexpr (I == 0) return x; else if constexpr (I == 1) return y; else assert(false); } template <std::size_t I> coordinate_t& get() { if constexpr (I == 0) return x; else if constexpr (I == 1) return y; else assert(false); } }; constexpr Point ZERO = { 0, 0 }; constexpr Point ONE = { 1, 0 }; constexpr Point I = { 0, 1 }; constexpr auto XY_COMPARATOR = [](const Point& p, const Point& q) { return p.x == q.x ? p.y < q.y : p.x < q.x; }; constexpr auto XY_COMPARATOR_GREATER = [](const Point& p, const Point& q) { return p.x == q.x ? p.y > q.y : p.x > q.x; }; constexpr auto YX_COMPARATOR = [](const Point& p, const Point& q) { return p.y == q.y ? p.x < q.x : p.y < q.y; }; constexpr auto YX_COMPARATOR_GREATER = [](const Point& p, const Point& q) { return p.y == q.y ? p.x > q.x : p.y > q.y; }; } // namespace suisen::integral_geometry namespace std { template <> struct tuple_size<suisen::integral_geometry::Point> : integral_constant<size_t, 2> {}; template <size_t I> struct tuple_element<I, suisen::integral_geometry::Point> { using type = suisen::integral_geometry::coordinate_t; }; } #line 8 "library/integral_geom/sort_points_by_argument.hpp" namespace suisen::integral_geometry { /** * 1. (x < 0, y = 0) -> pi * 2. (x = 0, y = 0) -> 0 * 3. points with same argument -> arbitrary order */ template <typename PointType, typename MultipliedType = long long> bool compare_by_atan2(const PointType &p, const PointType &q) { const auto &[x1, y1] = p; const auto &[x2, y2] = q; if ((y1 < 0) xor (y2 < 0)) return y1 < y2; if ((x1 < 0) xor (x2 < 0)) return (y1 >= 0) xor (x1 < x2); if (x1 == 0 and y1 == 0) return true; if (x2 == 0 and y2 == 0) return false; return (MultipliedType(y1) * x2 < MultipliedType(y2) * x1); } template <typename PointType, typename MultipliedType = long long> void sort_points_by_argument(std::vector<PointType> &points) { std::sort(points.begin(), points.end(), compare_by_atan2<PointType, MultipliedType>); } } // namespace suisen::integral_geometry