cpp/geometry/polygon.hpp

• View this file on GitHub
• Last update: 2024-11-23 22:11:34+09:00
• Include: #include "cpp/geometry/polygon.hpp"

Depends on

• cpp/geometry/line.hpp
• cpp/geometry/vector.hpp
• 共通ヘッダー (cpp/template/small_template.hpp)

Verified with

• cpp/verify/convex_hull.test.cpp

Code

#pragma once
#include "geometry/line.hpp"
#include "geometry/vector.hpp"

template <class T> using Polygon = vector<Vec2<T>>;
template <class T> using Points = vector<Vec2<T>>;

template <class T> Polygon<T> convex_hull(Points<T> &p, bool strict = true) {
  int n = p.size();
  if (n <= 2) {
    return p;
  }
  int k = 0;
  sort(p.begin(), p.end(), Vec2<T>::compare_x);
  vector<Vec2<T>> ch(2 * n);
  auto check = [&](int i) {
    return sign(Vec2<T>::cross(ch[k - 1] - ch[k - 2], p[i] - ch[k - 1])) <=
           -1 + strict;
  };
  for (int i = 0; i < n; ch[k++] = p[i++]) {
    while (k >= 2 && check(i)) {
      --k;
    }
  }
  for (int i = n - 2, t = k + 1; i >= 0; ch[k++] = p[i--]) {
    while (k >= t && check(i)) {
      --k;
    }
  }
  ch.resize(k - 1);
  return ch;
}

template <class T> T area(const Polygon<T> &s) {
  ld ret = 0;
  int n = (int)s.size();
  for (int i = 0; i < n; i++) {
    int j = i == n - 1 ? 0 : i + 1;
    ret += (s[j].y + s[i].y) * (s[j].x - s[i].x);
  }
  return -ret / 2;
}

template<class T> bool in_polygon(const Vec2<T> &p, const Polygon<T> &poly) {
  // (px, py) - (px, -inf) とpolyの交点数
  int cnt = 0;
  int n = poly.size();
  for(int i = 0; i < n; i++) {
    int j = i + 1 == n ? 0 : i + 1;
    if (sign(poly[i].x - poly[j].x) == 0) {
      continue;
    }
    // 左にEPSずらす
    if (((poly[i].x - EPS < p.x && p.x < poly[j].x - EPS) ||
         (poly[j].x - EPS < p.x && p.x < poly[i].x - EPS)) &&
        find_point(Line{poly[i], poly[j]}, p.x) < p.y) {
      cnt++;
    }
  }
  return cnt & 1;
}

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.0/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.0/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
  File "/opt/hostedtoolcache/Python/3.12.0/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.0/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 260, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: geometry/line.hpp: line -1: no such header

Back to top page