cpp/geometry/line.hpp

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

Depends on

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

Required by

• cpp/geometry/polygon.hpp

Verified with

• cpp/verify/convex_hull.test.cpp

Code

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

template <class T> struct Line {
  Vec2<T> p, q;

  Line(const Vec2<T> &p_, const Vec2<T> &q_) : p(p_), q(q_) { assert(p != q); }
};

// 交差する
template <class T>
optional<pair<T, T>> vector_intersection(const Line<T> &l, const Line<T> &m) {
  T cross = Vec2<T>::cross(l.q - l.p, m.q - m.p);
  if (sign(cross) == 0) {
    return nullopt;
  }
  T a = l.q.x - l.p.x;
  T b = -(m.q.x - m.p.x);
  T c = l.q.y - l.p.y;
  T d = -(m.q.y - m.p.y);
  T e = m.p.x - l.p.x;
  T f = m.p.y - l.p.y;
  T g = a * d - b * c;
  return pair<T, T>((d * e - b * f) / g, (a * f - c * e) / g);
}

// 交差する
template <class T>
optional<Vec2<T>> line_intersection(const Line<T> &l, const Line<T> &m) {
  auto vec_inter = vector_intersection(l, m);
  if (!vec_inter) {
    return nullopt;
  }
  return l.p + (l.q - l.p) * vec_inter->first;
}

// 内部で交差する
template <class T>
optional<Vec2<T>> segment_intersection(const Line<T> &l, const Line<T> &m) {
  auto vec_inter = vector_intersection(l, m);
  if (!vec_inter || vec_inter->first < 0 || 1 < vec_inter->first ||
      vec_inter->second < 0 || 1 < vec_inter->second) {
    return nullopt;
  }
  return l.p + (l.q - l.p) * vec_inter->first;
}

template <class T> T find_point(const Line<T> &l, T x) {
  assert(sign(l.p.x - l.q.x));
  T a = (l.q.y - l.p.y) / (l.q.x - l.p.x);
  T b = l.p.y - a * l.p.x;
  return a * x + b;
}

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/vector.hpp: line -1: no such header

Back to top page