Sort Points by Argument
(geometry/SortPointsbyArgument.hpp)

• View this file on GitHub
• Last update: 2026-03-25 13:12:44+09:00
• Include: #include "geometry/SortPointsbyArgument.hpp"

概要

todo

計算量

todo

Verified with

• verify/LibraryChecker/geometry/SortPointsbyArgument.test.cpp

Code

struct Point {
  long long x, y;
};

__int128_t cross(const Point& a, const Point& b) {
  return (__int128_t)a.x * b.y - (__int128_t)a.y * b.x;
}

template <auto f = less()>
bool cmp(const Point& a, const Point& b) {
  int ah = (f(a.y, 0) or (a.y == 0 and a.x > 0));
  int bh = (f(b.y, 0) or (b.y == 0 and b.x > 0));
  if (ah != bh) return ah > bh;
  __int128_t c = cross(a, b);
  if (c == 0) {
    return abs(a.x) + abs(a.y) < abs(b.x) + abs(b.y);
  } else {
    return c > 0;
  }
}

#line 1 "geometry/SortPointsbyArgument.hpp"
struct Point {
  long long x, y;
};

__int128_t cross(const Point& a, const Point& b) {
  return (__int128_t)a.x * b.y - (__int128_t)a.y * b.x;
}

template <auto f = less()>
bool cmp(const Point& a, const Point& b) {
  int ah = (f(a.y, 0) or (a.y == 0 and a.x > 0));
  int bh = (f(b.y, 0) or (b.y == 0 and b.x > 0));
  if (ah != bh) return ah > bh;
  __int128_t c = cross(a, b);
  if (c == 0) {
    return abs(a.x) + abs(a.y) < abs(b.x) + abs(b.y);
  } else {
    return c > 0;
  }
}

Back to top page