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

• View this file on GitHub
• Last update: 2022-12-15 22:18:37+09:00
• Include: #include "emthrm/geometry/argument_sort.hpp"

時間計算量

$O(N\log{N})$

仕様

名前	効果	備考
void argument_sort(std::vector<std::pair<int, int>>* ps);	点集合 $\mathrm{ps}$ に対して偏角ソートを行う。	$\arg(x) = \pi$ ($x < 0$), $\arg(0) = 0$ とする。

参考文献

• https://betrue12.hateblo.jp/entry/2020/01/05/151244
• https://github.com/beet-aizu/library/blob/78fef02c3ce4f982525361a55adbfc78faabfb93/geometry/argsort.cpp

Submissons

https://judge.yosupo.jp/submission/6794

Verified with

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

Code

#ifndef EMTHRM_GEOMETRY_ARGUMENT_SORT_HPP_
#define EMTHRM_GEOMETRY_ARGUMENT_SORT_HPP_

#include <algorithm>
#include <iterator>
#include <utility>
#include <vector>

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

#endif  // EMTHRM_GEOMETRY_ARGUMENT_SORT_HPP_

#line 1 "include/emthrm/geometry/argument_sort.hpp"



#include <algorithm>
#include <iterator>
#include <utility>
#include <vector>

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

Back to top page