計算幾何学/偏角ソート
(test/geometry/argument_sort.test.cpp)

• View this file on GitHub
• Last update: 2023-02-25 01:48:23+09:00
• Problem: https://judge.yosupo.jp/problem/sort_points_by_argument

Depends on

• 偏角ソート (include/emthrm/geometry/argument_sort.hpp)

Code

/*
 * @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;
}

Back to top page