C++ Library for Competitive Programming
View the Project on GitHub emthrm/cp-library
/* * @title 計算幾何学/偏角ソート * * verification-helper: PROBLEM https://judge.yosupo.jp/problem/sort_points_by_argument */ #include <iostream> #include <utility> #include <vector> #include "emthrm/geometry/argument_sort.hpp" int main() { int n; std::cin >> n; std::vector<std::pair<int, int>> ps(n); for (int i = 0; i < n; ++i) { std::cin >> ps[i].first >> ps[i].second; } emthrm::argument_sort(&ps); for (int i = 0; i < n; ++i) { std::cout << ps[i].first << ' ' << ps[i].second << '\n'; } return 0; }
#line 1 "test/geometry/argument_sort.test.cpp" /* * @title 計算幾何学/偏角ソート * * verification-helper: PROBLEM https://judge.yosupo.jp/problem/sort_points_by_argument */ #include <iostream> #include <utility> #include <vector> #line 1 "include/emthrm/geometry/argument_sort.hpp" #include <algorithm> #include <iterator> #line 8 "include/emthrm/geometry/argument_sort.hpp" namespace emthrm { void argument_sort(std::vector<std::pair<int, int>>* ps) { using Point = std::pair<int, int>; std::vector<Point> orthant[4]{}; for (const Point& p : *ps) { if (p.second >= 0) { orthant[p.first >= 0 ? 2 : 3].emplace_back(p); } else { orthant[p.first >= 0].emplace_back(p); } } ps->clear(); for (int i = 0; i < 4; ++i) { if (i == 2) { std::sort(orthant[i].begin(), orthant[i].end(), [](const Point& a, const Point& b) -> bool { if (a.first == 0 && a.second == 0) { return !(b.first == 0 && b.second == 0); } if (b.first == 0 && b.second == 0) return false; return static_cast<long long>(a.first) * b.second - static_cast<long long>(a.second) * b.first > 0; }); } else { std::sort(orthant[i].begin(), orthant[i].end(), [](const Point& a, const Point& b) -> bool { return static_cast<long long>(a.first) * b.second - static_cast<long long>(a.second) * b.first > 0; }); } std::copy(orthant[i].begin(), orthant[i].end(), std::back_inserter(*ps)); } } } // namespace emthrm #line 12 "test/geometry/argument_sort.test.cpp" int main() { int n; std::cin >> n; std::vector<std::pair<int, int>> ps(n); for (int i = 0; i < n; ++i) { std::cin >> ps[i].first >> ps[i].second; } emthrm::argument_sort(&ps); for (int i = 0; i < n; ++i) { std::cout << ps[i].first << ' ' << ps[i].second << '\n'; } return 0; }