cp-library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub rniya/cp-library

:heavy_check_mark: Sort Points by Argument
(src/geometry/sort_points_by_argument.hpp)

Depends on

Verified with

Code

#pragma once
#include <algorithm>
#include <numeric>
#include <utility>
#include <vector>
#include "Point.hpp"

namespace geometry {

template <typename T> std::vector<int> sort_points_by_argument(const std::vector<Point<T>>& P) {
    auto type = [](const Point<T>& p) {
        if (p.x == 0 and p.y == 0) return 0;
        return (p.y < 0 or (p.y == 0 and p.x > 0)) ? -1 : 1;
    };
    int n = P.size();
    std::vector<int> res(n);
    std::iota(begin(res), end(res), 0);
    std::sort(begin(res), end(res), [&](int l, int r) {
        int L = type(P[l]), R = type(P[r]);
        return L != R ? L < R : P[l].x * P[r].y > P[l].y * P[r].x;
    });
    return res;
}

template <typename T> std::vector<int> sort_points_by_argument(const std::vector<std::pair<T, T>>& P) {
    std::vector<Point<T>> tmp;
    for (const auto& [x, y] : P) tmp.emplace_back(x, y);
    return sort_points_by_argument(tmp);
}

}  // namespace geometry
#line 2 "src/geometry/sort_points_by_argument.hpp"
#include <algorithm>
#include <numeric>
#include <utility>
#include <vector>
#line 2 "src/geometry/Point.hpp"
#include <cassert>
#include <cmath>
#include <iostream>
#include <type_traits>

namespace geometry {

template <typename T> struct Point {
    static T EPS;

    static void set_eps(T eps) { EPS = eps; }

    T x, y;

    Point() {}

    Point(T x, T y) : x(x), y(y) {}

    Point operator+(const Point& p) const { return Point(x + p.x, y + p.y); }

    Point operator-(const Point& p) const { return Point(x - p.x, y - p.y); }

    Point operator*(T t) const { return Point(x * t, y * t); }

    Point operator/(T t) const { return Point(x / t, y / t); }

    bool operator==(const Point& p) const { return x == p.x and y == p.y; }

    bool operator!=(const Point& p) const { return not((*this) == p); }

    bool operator<(const Point& p) const { return x != p.x ? x < p.x : y < p.y; }

    friend std::istream& operator>>(std::istream& is, Point& p) { return is >> p.x >> p.y; }

    friend std::ostream& operator<<(std::ostream& os, const Point& p) { return os << p.x << ' ' << p.y; }

    T norm() { return std::sqrt(x * x + y * y); }

    T norm2() { return x * x + y * y; }

    T arg() { return std::atan2(y, x); }

    T dot(const Point& p) { return x * p.x + y * p.y; }

    T det(const Point& p) { return x * p.y - y * p.x; }

    Point perp() { return Point(-y, x); }

    Point unit() { return *this / norm(); }

    Point normal() { return perp().unit(); }

    Point rotate(T rad) { return Point(std::cos(rad) * x - std::sin(rad) * y, std::sin(rad) * x + std::cos(rad) * y); }
};

template <> double Point<double>::EPS = 1e-9;
template <> long double Point<long double>::EPS = 1e-12;
template <> int Point<int>::EPS = 0;
template <> long long Point<long long>::EPS = 0;

template <typename T> int sgn(T x) { return x < -Point<T>::EPS ? -1 : x > Point<T>::EPS ? 1 : 0; }

}  // namespace geometry
#line 7 "src/geometry/sort_points_by_argument.hpp"

namespace geometry {

template <typename T> std::vector<int> sort_points_by_argument(const std::vector<Point<T>>& P) {
    auto type = [](const Point<T>& p) {
        if (p.x == 0 and p.y == 0) return 0;
        return (p.y < 0 or (p.y == 0 and p.x > 0)) ? -1 : 1;
    };
    int n = P.size();
    std::vector<int> res(n);
    std::iota(begin(res), end(res), 0);
    std::sort(begin(res), end(res), [&](int l, int r) {
        int L = type(P[l]), R = type(P[r]);
        return L != R ? L < R : P[l].x * P[r].y > P[l].y * P[r].x;
    });
    return res;
}

template <typename T> std::vector<int> sort_points_by_argument(const std::vector<std::pair<T, T>>& P) {
    std::vector<Point<T>> tmp;
    for (const auto& [x, y] : P) tmp.emplace_back(x, y);
    return sort_points_by_argument(tmp);
}

}  // namespace geometry
Back to top page