偏角ソート (整数座標)
(library/integral_geom/sort_points_by_argument.hpp)

• View this file on GitHub
• Last update: 2026-06-01 17:03:55+09:00
• Include: #include "library/integral_geom/sort_points_by_argument.hpp"

偏角ソート (整数座標)

Verified with

• test/src/integral_geom/count_lattice_point/yuki1999.test.cpp
• test/src/integral_geom/sort_points_by_argument/sort_points_by_argument.test.cpp

Code

#ifndef SUISEN_SORT_POINTS_BY_ARGUMENT
#define SUISEN_SORT_POINTS_BY_ARGUMENT

#include <algorithm>
#include <vector>

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 (x2 == 0 and y2 == 0) return false;
        if (x1 == 0 and y1 == 0) return true;
        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>

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 (x2 == 0 and y2 == 0) return false;
        if (x1 == 0 and y1 == 0) return true;
        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

Back to top page