円および 2 円の交点の存在判定
(geometry/circle.hpp)

• View this file on GitHub
• Last update: 2026-06-08 17:59:24+09:00
• Include: #include "geometry/circle.hpp"

円および 2 円の交点の存在判定

使い方

• Circle(Point _p, Real _r): コンストラクタ。_p を中心、_r を半径とする円を構築する。
• int intersect(Circle c1, Circle c2): 円 c1 と c2 の交点の存在判定を行う関数。厳密には交点の存在判定ではなく、内接・外接も含めた分類を行う。
  • c1 と c2 の関係によってそれぞれ以下のような値が返る。
    • 小さい円が大きい円の内部に完全に含まれる場合: 0
    • 片方の円がもう片方の円に内接している（もしくは同一円である）場合: 1
    • 2 円が 2 点で交わる場合: 2
    • 片方の円がもう片方の円に外接している場合: 3
    • 2 円が外部で離れている場合: 4
  • c1 と c2 が異なる円であれば、返り値は c1 と c2 の共通接線の個数と一致する。ただし、c1 と c2 が同一円である場合は共通接線は無限個存在するが、返り値は 1 である。
  • c1 と c2 が 1 個以上の交点を持つのは、返り値が 1, 2, 3 のどれかの場合である。1 または 3 であれば交点は 1 点、2 であれば交点は 2 点である（c1 と c2 が同一円である場合を除く）。
• pair<Point, Point> crosspoint(const Circle& c1, const Circle& c2): 円 c1 と c2 の交点 2 点を返す関数。
  • 必ず 2 点の組を返す。ただし、intersect(c1, c2) の返り値によっては、同じ点 2 点からなる組や実際には c1 と c2 の交点でない点を含む組が返る可能性がある。
    • intersect(c1, c2) の返り値が 2 であれば、c1 と c2 の交点 2 点の組を返す。
    • c1 と c2 が同一円ではなく、intersect(c1, c2) の返り値が 1 または 3 であれば、first と second が等しく、両方とも c1 と c2 の唯一の交点となる点（接点）である組を返す。
    • 同心円、同一円や半径 0 の円を与えると 0 除算や NaN が発生しうる。そのような c1 と c2 を与えることや、返り値を交点として使用することは推奨されない。

Depends on

• geometry/geometry-base.hpp

Code

#pragma once

#include "geometry-base.hpp"

struct Circle {
  Point p;
  Real r;

  Circle() = default;
  Circle(Point _p, Real _r) : p(_p), r(_r) {}
};

using Circles = vector<Circle>;

int intersect(Circle c1, Circle c2) {
  if (c1.r < c2.r) swap(c1, c2);
  Real d = abs(c1.p - c2.p);
  if (c1.r + c2.r < d) return 4;
  if (equals(c1.r + c2.r, d)) return 3;
  if (c1.r - c2.r < d) return 2;
  if (equals(c1.r - c2.r, d)) return 1;
  return 0;
}

pair<Point, Point> crosspoint(const Circle& c1, const Circle& c2) {
  Real d = abs(c1.p - c2.p);
  Real x = (c1.r * c1.r + d * d - c2.r * c2.r) / (2 * c1.r * d);
  if (abs(x) > 1) x = (x > 0 ? 1.0 : -1.0);
  Real a = acos(x);
  Real t = atan2(c2.p.imag() - c1.p.imag(), c2.p.real() - c1.p.real());
  Point p1 = c1.p + Point(cos(t + a) * c1.r, sin(t + a) * c1.r);
  Point p2 = c1.p + Point(cos(t - a) * c1.r, sin(t - a) * c1.r);
  return {p1, p2};
}

/**
 * @brief 円および 2 円の交点の存在判定
 */

#line 2 "geometry/circle.hpp"

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

#include <algorithm>
#include <cassert>
#include <cmath>
#include <complex>
#include <iostream>
#include <vector>
using namespace std;

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

template <typename 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 {x + r.x, y + r.y}; }
  P operator-(const P& r) const { return {x - r.x, y - r.y}; }
  P operator*(R r) const { return {x * r, y * r}; }
  P operator/(R r) const { return {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)};
  }

  R real() const { return x; }
  R imag() const { return y; }
  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>;

// ccw, 点の進行方向
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;                 // 反時計回り
  if (cross(x, y) < -EPS) return -1;                // 時計回り
  if (min(norm(x), norm(y)) < EPS * EPS) return 0;  // c=a または c=b
  if (dot(x, y) < EPS) return +2;                   // c-a-b の順で一直線
  if (norm(x) < norm(y)) return -2;                 // a-b-c の順で一直線
  return 0;                                         // a-c-b の順で一直線
}
#line 4 "geometry/circle.hpp"

struct Circle {
  Point p;
  Real r;

  Circle() = default;
  Circle(Point _p, Real _r) : p(_p), r(_r) {}
};

using Circles = vector<Circle>;

int intersect(Circle c1, Circle c2) {
  if (c1.r < c2.r) swap(c1, c2);
  Real d = abs(c1.p - c2.p);
  if (c1.r + c2.r < d) return 4;
  if (equals(c1.r + c2.r, d)) return 3;
  if (c1.r - c2.r < d) return 2;
  if (equals(c1.r - c2.r, d)) return 1;
  return 0;
}

pair<Point, Point> crosspoint(const Circle& c1, const Circle& c2) {
  Real d = abs(c1.p - c2.p);
  Real x = (c1.r * c1.r + d * d - c2.r * c2.r) / (2 * c1.r * d);
  if (abs(x) > 1) x = (x > 0 ? 1.0 : -1.0);
  Real a = acos(x);
  Real t = atan2(c2.p.imag() - c1.p.imag(), c2.p.real() - c1.p.real());
  Point p1 = c1.p + Point(cos(t + a) * c1.r, sin(t + a) * c1.r);
  Point p2 = c1.p + Point(cos(t - a) * c1.r, sin(t - a) * c1.r);
  return {p1, p2};
}

/**
 * @brief 円および 2 円の交点の存在判定
 */

Back to top page