library
This documentation is automatically generated by online-judge-tools/verification-helper
Geometry/Circle.hpp
- View this file on GitHub
- Last update: 2021-03-21 09:12:36+09:00
- Include:
#include "Geometry/Circle.hpp"
Depends on
Required by
- Geometry/Geometric.cpp
- Geometry/Triangle.hpp
- Geometry/area_of_intersection.cpp
- Geometry/closest_pair.cpp
- Geometry/common_tangent.cpp
Verified with
- test/Geometric_area_of_intersection_between_circle_and_polygon.test.cpp
- test/Geometric_area_of_intersection_between_two_circles.test.cpp
- test/Geometric_cirnnumscribed_circle.test.cpp
- test/Geometric_closest_pair.test.cpp
- test/Geometric_common_tangent.test.cpp
- test/Geometric_convex_hull.test.cpp
- test/Geometric_cross_point_of_circles.test.cpp
- test/Geometric_cross_points_between_line_and_circle.test.cpp
- test/Geometric_dot_cross.test.cpp
- test/Geometric_iSP.test.cpp
- test/Geometric_incircle_of_triangle.test.cpp
- test/Geometric_is_convex.test.cpp
- test/Geometric_is_parallel_is_orthogonal.test.cpp
- test/Geometric_line_intersection.test.cpp
- test/Geometric_polygon_cut.test.cpp
- test/Geometric_polygon_diameter.test.cpp
- test/Geometric_polygon_point_containment.test.cpp
- test/Geometric_projection.test.cpp
- test/Geometric_reflection.test.cpp
- test/Geometric_segment_distance.test.cpp
- test/Geometric_segment_intersection.test.cpp
- test/Geometric_tangent_to_circle.test.cpp
Code
#pragma once
#include "./Geometric.hpp"
#include "./Vec2.hpp"
#include <iostream>
namespace Geometric {
struct Circle {
Vec2 center;
LD r;
constexpr Circle() : center(), r(0) {}
constexpr Circle(LD _r) : center(), r(_r) {}
constexpr Circle(LD _x, LD _y, LD _r) : center(_x, _y), r(_r) {}
constexpr Circle(const Vec2& _c, LD _r) : center(_c), r(_r) {}
constexpr bool operator==(const Circle& c) const {
return center == c.center && sgn(r - c.r) == 0;
}
constexpr bool operator!=(const Circle& c) const {
return !(*this == c);
}
constexpr Circle& operator+(const Vec2& v) const {
return Circle(*this) += v;
}
constexpr Circle& operator-(const Vec2& v) const {
return Circle(*this) -= v;
}
constexpr Circle& operator+=(const Vec2& v) {
center += v;
return *this;
}
constexpr Circle& operator-=(const Vec2& v) {
center -= v;
return *this;
}
constexpr LD top_y() const {
return center.y - r;
}
constexpr LD bottom_y() const {
return center.y + r;
}
constexpr LD left_x() const {
return center.x - r;
}
constexpr LD right_x() const {
return center.x + r;
}
constexpr Vec2 top() const {
return center - Vec2(0, r);
}
constexpr Vec2 bottom() const {
return center + Vec2(0, r);
}
constexpr Vec2 left() const {
return center - Vec2(r, 0);
}
constexpr Vec2 right() const {
return center + Vec2(r, 0);
}
constexpr LD area() const {
return r * r * PI;
}
constexpr LD perimeter() const {
return 2 * r * PI;
}
// c が this に含まれる（一致するときも true を返す）
bool contains(const Circle& c) const {
return sgn(distance(center, c.center) + c.r - r) <= 0;
}
friend std::ostream& operator<<(std::ostream& os, const Circle& c) {
return os << '(' << c.center.x << ", " << c.center.y << ", " << c.r << ')';
}
friend std::istream& operator>>(std::istream& is, Circle& c) {
return is >> c.center >> c.r;
}
};
} // namespace Geometric#line 2 "Geometry/Geometric.hpp"
#include <iostream>
#include <vector>
#include <algorithm>
#include <optional>
namespace Geometric {
using LD = long double;
constexpr long double PI = 3.14159265358979323846, EPS = 1e-12;
// a > 0 : +1
// a = 0 : 0
// a < 0 : -1
constexpr int sgn(LD a);
constexpr LD deg_to_rad(LD deg);
constexpr LD rad_to_deg(LD rad);
struct Vec2;
struct Line;
struct Segment;
struct Rect;
struct Circle;
struct Polygon;
// AB から見て BC が左に曲がる : +1
// AB から見て BC が右に曲がる : -1
// ABC, CBA の順に一直線上に並ぶ : +2
// ACB, BCA の順に一直線上に並ぶ : 0
// BAC, CAB の順に一直線上に並ぶ : -2
int iSP(const Vec2& a, const Vec2& b, const Vec2& c);
// ∠ABC が鋭角 : 0, 直角 : 1, 鈍角 : 2
int angle_type(const Vec2& a, const Vec2& b, const Vec2& c);
// ∠ABC の値 (radian)
LD angle(const Vec2& a, const Vec2& b, const Vec2& c);
// 距離
LD distance(const Vec2& v1, const Vec2& v2);
LD distance(const Vec2& v, const Line& l);
LD distance(const Vec2& v, const Segment& s);
LD distance(const Vec2& v, const Circle& c);
LD distance(const Line& l, const Vec2& v);
LD distance(const Line& l1, const Line& l2);
LD distance(const Segment& s, const Vec2& v);
LD distance(const Segment& s1, const Segment& s2);
LD distance(const Circle& c, const Vec2& v);
LD distance(const Circle& c1, const Circle& c2);
// 交差判定 （内包しているときも true を返す）
bool intersect(const Vec2& v1, const Vec2& v2);
bool intersect(const Vec2& v, const Line& l);
bool intersect(const Vec2& v, const Segment& l);
bool intersect(const Vec2& v, const Circle& c);
bool intersect(const Vec2& v, const Rect& r);
bool intersect(const Vec2& v, const Polygon& p);
bool intersect(const Line& l, const Vec2& v);
bool intersect(const Line& l1, const Line& l2);
bool intersect(const Line& l, const Circle& c);
bool intersect(const Segment& l, const Vec2& v);
bool intersect(const Segment& s1, const Segment& s2);
bool intersect(const Segment& s, const Circle& c);
bool intersect(const Circle& c, const Vec2& v);
bool intersect(const Circle& c, const Line& l);
bool intersect(const Circle& c, const Segment& s);
bool intersect(const Circle& c1, const Circle& c2);
bool intersect(const Circle& c, const Rect& r);
bool intersect(const Rect& r, const Vec2& v);
bool intersect(const Rect& r1, const Rect& r2);
bool intersect(const Rect& r, const Circle& c);
bool intersect(const Polygon& p, const Vec2& v);
// 接するか判定
bool tangent(const Vec2& v1, const Vec2& v2);
bool tangent(const Vec2& v, const Line& l);
bool tangent(const Vec2& v, const Segment& l);
bool tangent(const Vec2& v, const Circle& c);
bool tangent(const Vec2& v, const Rect& r);
bool tangent(const Vec2& v, const Polygon& p);
bool tangent(const Line& l, const Vec2& v);
bool tangent(const Line& l, const Circle& c);
bool tangent(const Line& l, const Rect& r);
bool tangent(const Segment& l, const Vec2& v);
bool tangent(const Circle& c, const Vec2& v);
bool tangent(const Circle& c, const Line& l);
bool tangent(const Circle& c1, const Circle& c2);
bool tangent(const Rect& r, const Vec2& v);
bool tangent(const Rect& r, const Line& l);
bool tangent(const Polygon& p, const Vec2& v);
// 交点
std::optional<Vec2> cross_point(const Line& l1, const Line& l2);
std::optional<Vec2> cross_point(const Segment& s1, const Segment& s2);
std::vector<Vec2> cross_points(const Line& l, const Circle& c);
std::vector<Vec2> cross_points(const Segment& s, const Circle& c);
std::vector<Vec2> cross_points(const Circle& c, const Line& l);
std::vector<Vec2> cross_points(const Circle& c, const Segment& s);
std::vector<Vec2> cross_points(const Circle& c1, const Circle& c2);
// 円の接線
std::vector<Vec2> tangent_to_circle(const Circle& c, const Vec2& v);
} // namespace Geometric
#line 4 "Geometry/Vec2.hpp"
#include <utility>
#include <cmath>
namespace Geometric {
struct Vec2 {
LD x, y;
static constexpr bool compare_x(const Vec2& v1, const Vec2& v2) {
return v1.x < v2.x;
}
static constexpr bool compare_y(const Vec2& v1, const Vec2& v2) {
return v1.y < v2.y;
}
static constexpr bool compare_xy(const Vec2& v1, const Vec2& v2) {
return std::make_pair(v1.x, v1.y) < std::make_pair(v2.x, v2.y);
}
static constexpr bool compare_yx(const Vec2& v1, const Vec2& v2) {
return std::make_pair(v1.y, v1.x) < std::make_pair(v2.y, v2.x);
}
static constexpr Vec2 zero() {
return Vec2(0, 0);
}
constexpr Vec2() : x(0), y(0) {}
constexpr Vec2(LD _x, LD _y) : x(_x), y(_y) {}
Vec2(LD rad) : x(std::cos(rad)), y(std::sin(rad)) {}
constexpr bool operator==(const Vec2& v) const {
return sgn(x - v.x) == 0 && sgn(y - v.y) == 0;
}
constexpr bool operator!=(const Vec2& v) const {
return !(*this == v);
}
constexpr Vec2 operator+() const {
return *this;
}
constexpr Vec2 operator-() const {
return {-x, -y};
}
constexpr Vec2 operator+(const Vec2& v) const {
return Vec2(*this) += v;
}
constexpr Vec2 operator-(const Vec2& v) const {
return Vec2(*this) -= v;
}
constexpr Vec2 operator*(const Vec2& v) const {
return Vec2(*this) *= v;
}
constexpr Vec2 operator/(const Vec2& v) const {
return Vec2(*this) /= v;
}
constexpr Vec2 operator+(LD n) const {
return Vec2(*this) += n;
}
constexpr Vec2 operator-(LD n) const {
return Vec2(*this) -= n;
}
constexpr Vec2 operator*(LD n) const {
return Vec2(*this) *= n;
}
constexpr Vec2 operator/(LD n) const {
return Vec2(*this) /= n;
}
constexpr Vec2& operator+=(const Vec2& v) {
x += v.x;
y += v.y;
return *this;
}
constexpr Vec2& operator-=(const Vec2& v) {
x -= v.x;
y -= v.y;
return *this;
}
constexpr Vec2& operator*=(const Vec2& v) {
x *= v.x;
y *= v.y;
return *this;
}
constexpr Vec2& operator/=(const Vec2& v) {
x /= v.x;
y /= v.y;
return *this;
}
constexpr Vec2& operator+=(LD n) {
x += n;
y += n;
return *this;
}
constexpr Vec2& operator-=(LD n) {
x -= n;
y -= n;
return *this;
}
constexpr Vec2& operator*=(LD n) {
x *= n;
y *= n;
return *this;
}
constexpr Vec2& operator/=(LD n) {
x /= n;
y /= n;
return *this;
}
constexpr LD operator[](size_t i) const {
return i == 0 ? x : i == 1 ? y : 0;
}
constexpr std::pair<LD, LD> pair() const {
return {x, y};
}
LD manhattan(const Vec2& v) const {
return std::abs(x - v.x) + std::abs(y - v.y);
}
constexpr LD length_square() const {
return dot(*this);
}
LD length() const {
return std::sqrt(length_square());
}
// 内積
constexpr LD dot(const Vec2& v) const {
return x * v.x + y * v.y;
}
// 外積
constexpr LD cross(const Vec2& v) const {
return x * v.y - y * v.x;
}
// 正規化（長さを1にした）ベクトル
Vec2 normalized() const {
return *this / length();
}
// 原点中心に rad 回転した座標
Vec2 rotation(LD rad) const {
LD c = std::cos(rad), s = std::sin(rad);
return {x * c - y * s, x * s + y * c};
}
// 原点中心の円上に乗っているとしたときの偏角
LD angle() const {
return std::atan2(y, x);
}
// 正射影
Vec2 projection(const Line& l) const;
// 鏡映変換
Vec2 reflection(const Line& l) const;
constexpr Vec2 rotate90() const {
return {y, -x};
}
constexpr Vec2 rotate180() const {
return {-x, -y};
}
constexpr Vec2 rotate270() const {
return {-y, x};
}
friend std::ostream& operator<<(std::ostream& os, const Vec2& v) {
return os << '(' << v.x << ", " << v.y << ')';
}
friend std::istream& operator>>(std::istream& is, Vec2& v) {
return is >> v.x >> v.y;
}
};
} // namespace Geometric
#line 5 "Geometry/Circle.hpp"
namespace Geometric {
struct Circle {
Vec2 center;
LD r;
constexpr Circle() : center(), r(0) {}
constexpr Circle(LD _r) : center(), r(_r) {}
constexpr Circle(LD _x, LD _y, LD _r) : center(_x, _y), r(_r) {}
constexpr Circle(const Vec2& _c, LD _r) : center(_c), r(_r) {}
constexpr bool operator==(const Circle& c) const {
return center == c.center && sgn(r - c.r) == 0;
}
constexpr bool operator!=(const Circle& c) const {
return !(*this == c);
}
constexpr Circle& operator+(const Vec2& v) const {
return Circle(*this) += v;
}
constexpr Circle& operator-(const Vec2& v) const {
return Circle(*this) -= v;
}
constexpr Circle& operator+=(const Vec2& v) {
center += v;
return *this;
}
constexpr Circle& operator-=(const Vec2& v) {
center -= v;
return *this;
}
constexpr LD top_y() const {
return center.y - r;
}
constexpr LD bottom_y() const {
return center.y + r;
}
constexpr LD left_x() const {
return center.x - r;
}
constexpr LD right_x() const {
return center.x + r;
}
constexpr Vec2 top() const {
return center - Vec2(0, r);
}
constexpr Vec2 bottom() const {
return center + Vec2(0, r);
}
constexpr Vec2 left() const {
return center - Vec2(r, 0);
}
constexpr Vec2 right() const {
return center + Vec2(r, 0);
}
constexpr LD area() const {
return r * r * PI;
}
constexpr LD perimeter() const {
return 2 * r * PI;
}
// c が this に含まれる（一致するときも true を返す）
bool contains(const Circle& c) const {
return sgn(distance(center, c.center) + c.r - r) <= 0;
}
friend std::ostream& operator<<(std::ostream& os, const Circle& c) {
return os << '(' << c.center.x << ", " << c.center.y << ", " << c.r << ')';
}
friend std::istream& operator>>(std::istream& is, Circle& c) {
return is >> c.center >> c.r;
}
};
} // namespace Geometric