二次元幾何の基本要素
(geometry/geometry-base.hpp)

• View this file on GitHub
• Last update: 2026-07-15 19:23:28+09:00
• Include: #include "geometry/geometry-base.hpp"

二次元幾何で用いる点とベクトルの基本演算を扱う．

二次元平面上の点とベクトルを Point で表す．座標型は long double で，誤差判定には EPS = 1e-10 を用いる．

• dot(a, b)：内積を返す．
• cross(a, b)：外積を返す．
• abs(p)：ベクトルの長さを返す．
• norm(p)：ベクトルの長さの二乗を返す．
• arg(p)：偏角を返す．
• p.rotate(rad)：p を反時計回りに rad 回転する．
• p.rotate90()：p を反時計回りに $90$ 度回転する．
• ccw(a, b, c)：有向直線 $a\to b$ に対する $c$ の位置を返す．反時計回りなら $1$，時計回りなら $-1$，一直線上で $c-a-b$ の順なら $2$，$a-b-c$ の順なら $-2$，線分 $ab$ 上なら $0$．

資料

• geometry/geometry-base.hpp - Nyaan’s Library

Required by

• 三次元幾何の基本要素 (geometry-3d/geometry-base.hpp)
• 三次元空間上の直線 (geometry-3d/line.hpp)
• 三次元空間上の平面 (geometry-3d/plane.hpp)
• 三次元空間上の線分 (geometry-3d/segment.hpp)
• 三次元空間上の円と球 (geometry-3d/sphere.hpp)
• 三次元空間上の三角形 (geometry-3d/triangle.hpp)
• 円 (geometry/circle.hpp)
• 半平面交差 (geometry/halfplane-intersection.hpp)
• 直線 (geometry/line.hpp)
• 多角形 (geometry/polygon.hpp)
• 線分 (geometry/segment.hpp)

Verified with

• verify/geometry-3d/UNIT_geometry_3d.test.cpp
• verify/geometry/AOJ_CGL_1_A.test.cpp
• verify/geometry/AOJ_CGL_1_B.test.cpp
• verify/geometry/AOJ_CGL_1_C.test.cpp
• verify/geometry/AOJ_CGL_2_A.test.cpp
• verify/geometry/AOJ_CGL_2_B.test.cpp
• verify/geometry/AOJ_CGL_2_C.test.cpp
• verify/geometry/AOJ_CGL_2_D.test.cpp
• verify/geometry/AOJ_CGL_3_A.test.cpp
• verify/geometry/AOJ_CGL_3_B.test.cpp
• verify/geometry/AOJ_CGL_3_C.test.cpp
• verify/geometry/AOJ_CGL_4_A.test.cpp
• verify/geometry/AOJ_CGL_4_B.test.cpp
• verify/geometry/AOJ_CGL_4_C.test.cpp
• verify/geometry/AOJ_CGL_7_A.test.cpp
• verify/geometry/AOJ_CGL_7_D.test.cpp
• verify/geometry/AOJ_CGL_7_E.test.cpp
• verify/geometry/AOJ_CGL_7_F.test.cpp
• verify/geometry/AOJ_CGL_7_G.test.cpp
• verify/geometry/AOJ_CGL_7_I.test.cpp
• verify/geometry/UNIT_halfplane_intersection.test.cpp
• verify/geometry/UNIT_polygon.test.cpp

Code

#pragma once

#include <bits/stdc++.h>

using Real = long double;
constexpr Real EPS = 1e-10;
constexpr Real PI = 3.141592653589793238462643383279L;
bool equals(Real x, Real y) { return fabs(x - y) < EPS; }
int sign(Real a) { return equals(a, 0) ? 0 : (a > 0 ? 1 : -1); }

template <class R>
struct PointBase {
  using P = PointBase;
  R x, y;
  PointBase() : x(0), y(0) {}
  PointBase(R _x, R _y) : x(_x), y(_y) {}
  template <typename T, typename U>
  PointBase(const pair<T, U>& p) : x(p.first), y(p.second) {}

  P operator+(const P& r) const { return P{x + r.x, y + r.y}; }
  P operator-(const P& r) const { return P{x - r.x, y - r.y}; }
  P operator-() const { return P{-x, -y}; }
  P operator*(R r) const { return P{x * r, y * r}; }
  P operator/(R r) const { return P{x / r, y / r}; }

  P& operator+=(const P& r) { return (*this) = (*this) + r; }
  P& operator-=(const P& r) { return (*this) = (*this) - r; }
  P& operator*=(R r) { return (*this) = (*this) * r; }
  P& operator/=(R r) { return (*this) = (*this) / r; }

  bool operator<(const P& r) const { return x != r.x ? x < r.x : y < r.y; }
  bool operator==(const P& r) const { return x == r.x and y == r.y; }
  bool operator!=(const P& r) const { return !((*this) == r); }

  P rotate(R rad) const {
    return {x * cos(rad) - y * sin(rad), x * sin(rad) + y * cos(rad)};
  }
  P rotate90() const { return {-y, x}; }

  R real() const { return x; }
  R imag() const { return y; }

  friend P operator*(R r, const P& p) { return p * r; }
  friend R real(const P& p) { return p.x; }
  friend R imag(const P& p) { return p.y; }
  friend R dot(const P& l, const P& r) { return l.x * r.x + l.y * r.y; }
  friend R cross(const P& l, const P& r) { return l.x * r.y - l.y * r.x; }
  friend R abs(const P& p) { return sqrt(p.x * p.x + p.y * p.y); }
  friend R norm(const P& p) { return p.x * p.x + p.y * p.y; }
  friend R arg(const P& p) { return atan2(p.y, p.x); }

  friend istream& operator>>(istream& is, P& p) {
    R a, b;
    is >> a >> b;
    p = P{a, b};
    return is;
  }
  friend ostream& operator<<(ostream& os, const P& p) {
    return os << p.x << " " << p.y;
  }
};
using Point = PointBase<Real>;
using Points = vector<Point>;

// relative position of c from a->b
int ccw(const Point& a, const Point& b, const Point& c) {
  Point x = b - a, y = c - a;
  if (cross(x, y) > EPS) return +1;        // counter-clockwise
  if (cross(x, y) < -EPS) return -1;       // clockwise
  if (dot(x, y) < -EPS) return +2;         // collinear in the order c-a-b
  if (norm(x) + EPS < norm(y)) return -2;  // collinear in the order a-b-c
  return 0;                                // collinear in the order a-c-b
}

/**
 * @brief 二次元幾何の基本要素
 * @docs docs/geometry/geometry-base.md
 */

#line 2 "geometry/geometry-base.hpp"

#include <bits/stdc++.h>

using Real = long double;
constexpr Real EPS = 1e-10;
constexpr Real PI = 3.141592653589793238462643383279L;
bool equals(Real x, Real y) { return fabs(x - y) < EPS; }
int sign(Real a) { return equals(a, 0) ? 0 : (a > 0 ? 1 : -1); }

template <class R>
struct PointBase {
  using P = PointBase;
  R x, y;
  PointBase() : x(0), y(0) {}
  PointBase(R _x, R _y) : x(_x), y(_y) {}
  template <typename T, typename U>
  PointBase(const pair<T, U>& p) : x(p.first), y(p.second) {}

  P operator+(const P& r) const { return P{x + r.x, y + r.y}; }
  P operator-(const P& r) const { return P{x - r.x, y - r.y}; }
  P operator-() const { return P{-x, -y}; }
  P operator*(R r) const { return P{x * r, y * r}; }
  P operator/(R r) const { return P{x / r, y / r}; }

  P& operator+=(const P& r) { return (*this) = (*this) + r; }
  P& operator-=(const P& r) { return (*this) = (*this) - r; }
  P& operator*=(R r) { return (*this) = (*this) * r; }
  P& operator/=(R r) { return (*this) = (*this) / r; }

  bool operator<(const P& r) const { return x != r.x ? x < r.x : y < r.y; }
  bool operator==(const P& r) const { return x == r.x and y == r.y; }
  bool operator!=(const P& r) const { return !((*this) == r); }

  P rotate(R rad) const {
    return {x * cos(rad) - y * sin(rad), x * sin(rad) + y * cos(rad)};
  }
  P rotate90() const { return {-y, x}; }

  R real() const { return x; }
  R imag() const { return y; }

  friend P operator*(R r, const P& p) { return p * r; }
  friend R real(const P& p) { return p.x; }
  friend R imag(const P& p) { return p.y; }
  friend R dot(const P& l, const P& r) { return l.x * r.x + l.y * r.y; }
  friend R cross(const P& l, const P& r) { return l.x * r.y - l.y * r.x; }
  friend R abs(const P& p) { return sqrt(p.x * p.x + p.y * p.y); }
  friend R norm(const P& p) { return p.x * p.x + p.y * p.y; }
  friend R arg(const P& p) { return atan2(p.y, p.x); }

  friend istream& operator>>(istream& is, P& p) {
    R a, b;
    is >> a >> b;
    p = P{a, b};
    return is;
  }
  friend ostream& operator<<(ostream& os, const P& p) {
    return os << p.x << " " << p.y;
  }
};
using Point = PointBase<Real>;
using Points = vector<Point>;

// relative position of c from a->b
int ccw(const Point& a, const Point& b, const Point& c) {
  Point x = b - a, y = c - a;
  if (cross(x, y) > EPS) return +1;        // counter-clockwise
  if (cross(x, y) < -EPS) return -1;       // clockwise
  if (dot(x, y) < -EPS) return +2;         // collinear in the order c-a-b
  if (norm(x) + EPS < norm(y)) return -2;  // collinear in the order a-b-c
  return 0;                                // collinear in the order a-c-b
}

/**
 * @brief 二次元幾何の基本要素
 * @docs docs/geometry/geometry-base.md
 */

Back to top page