library
This documentation is automatically generated by online-judge-tools/verification-helper
test/Geometric_cross_points_between_line_and_circle.test.cpp
- View this file on GitHub
- Last update: 2021-03-21 09:12:36+09:00
- Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/4/CGL/all/CGL_7_D
Depends on
- Geometry/Circle.hpp
- Geometry/Geometric.cpp
- Geometry/Geometric.hpp
- Geometry/Line.hpp
- Geometry/Polygon.hpp
- Geometry/Rect.hpp
- Geometry/Triangle.hpp
- Geometry/Vec2.hpp
Code
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/4/CGL/all/CGL_7_D"
#define ERROR "1e-6"
#include "./../Geometry/Line.hpp"
#include "./../Geometry/Circle.hpp"
#include "./../Geometry/Geometric.cpp"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
using namespace std;
int main() {
Geometric::Circle c;
cin >> c;
int q;
cin >> q;
while (q--) {
Geometric::Line l;
cin >> l;
auto ans = cross_points(c, l);
assert(1 <= ans.size() && ans.size() <= 2);
if (ans.size() == 1) {
ans.push_back(ans[0]);
} else {
sort(ans.begin(), ans.end(), Geometric::Vec2::compare_xy);
}
printf("%.12Lf %.12Lf %.12Lf %.12Lf\n", ans[0].x, ans[0].y, ans[1].x, ans[1].y);
}
}#line 1 "test/Geometric_cross_points_between_line_and_circle.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/4/CGL/all/CGL_7_D"
#define ERROR "1e-6"
#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 6 "Geometry/Line.hpp"
#include <tuple>
#line 8 "Geometry/Line.hpp"
namespace Geometric {
namespace internal {
struct LineBase {
protected:
constexpr LineBase() = default;
constexpr LineBase(const Vec2& _begin, const Vec2& _end)
: begin(_begin), end(_end) {}
constexpr LineBase(LD begin_x, LD begin_y, LD end_x, LD end_y)
: begin(begin_x, begin_y), end(end_x, end_y) {}
public:
Vec2 begin, end;
constexpr LineBase operator+(const Vec2& v) {
return LineBase(*this) += v;
}
constexpr LineBase operator-(const Vec2& v) {
return LineBase(*this) -= v;
}
constexpr LineBase& operator+=(const Vec2& v) {
begin += v;
end += v;
return *this;
}
constexpr LineBase& operator-=(const Vec2& v) {
begin -= v;
end -= v;
return *this;
}
constexpr Vec2 vec() const {
return end - begin;
}
constexpr Vec2 counter_vec() const {
return begin - end;
}
// 平行判定
constexpr bool is_parallel(const LineBase& l) const {
return sgn(vec().cross(l.vec())) == 0;
}
// 直交判定
constexpr bool is_orthogonal(const LineBase& l) const {
return sgn(vec().dot(l.vec())) == 0;
}
friend std::ostream& operator<<(std::ostream& os, const LineBase& l) {
return os << '(' << l.begin << ", " << l.end << ')';
}
friend std::istream& operator>>(std::istream& is, LineBase& l) {
return is >> l.begin >> l.end;
}
};
} // namespace internal
struct Line : internal::LineBase {
constexpr Line() = default;
constexpr Line(const Vec2& _begin, const Vec2& _end) : LineBase(_begin, _end) {}
constexpr Line(LD begin_x, LD begin_y, LD end_x, LD end_y)
: LineBase(begin_x, begin_y, end_x, end_y) {}
constexpr Line(const LineBase& l) : LineBase(l) {}
// ax + by + c = 0 の式に変形する
std::tuple<LD, LD, LD> abc() const {
if (sgn(begin.x - end.x) == 0) {
return {1, 0, -begin.x};
} else {
LD slope = (end.y - begin.y) / (end.x - begin.x);
return {slope, -1, begin.y - begin.x * slope};
}
}
};
struct Segment : internal::LineBase {
constexpr Segment() = default;
constexpr Segment(const Vec2& _begin, const Vec2& _end) : LineBase(_begin, _end) {}
constexpr Segment(LD begin_x, LD begin_y, LD end_x, LD end_y)
: LineBase(begin_x, begin_y, end_x, end_y) {}
constexpr Segment(const LineBase& l) : LineBase(l) {}
};
} // 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
#line 6 "Geometry/Rect.hpp"
namespace Geometric {
struct Rect {
Vec2 pos, size;
constexpr Rect() {}
constexpr Rect(LD _w, LD _h) : size(_w, _h) {}
constexpr Rect(const Vec2& _size) : size(_size) {}
constexpr Rect(LD _x, LD _y, LD _w, LD _h) : pos(_x, _y), size(_w, _h) {}
constexpr Rect(const Vec2& _pos, const Vec2& _size) : pos(_pos), size(_size) {}
constexpr bool operator==(const Rect& r) const {
return pos == r.pos && size == r.size;
}
constexpr bool operator!=(const Rect& r) const {
return !(*this == r);
}
constexpr Rect operator+(const Vec2& v) const {
return Rect(*this) += v;
}
constexpr Rect operator-(const Vec2& v) const {
return Rect(*this) -= v;
}
constexpr Rect& operator+=(const Vec2& v) {
pos += v;
return *this;
}
constexpr Rect& operator-=(const Vec2& v) {
pos -= v;
return *this;
}
constexpr Rect& set_center(const Vec2& _pos) {
pos = _pos - size / 2;
return *this;
}
constexpr LD left_x() const {
return pos.x;
}
constexpr LD right_x() const {
return pos.x + size.x;
}
constexpr LD top_y() const {
return pos.y;
}
constexpr LD bottom_y() const {
return pos.y + size.y;
}
constexpr Vec2 top_left() const {
return pos;
}
constexpr Vec2 top_right() const {
return pos + Vec2(size.x, 0);
}
constexpr Vec2 bottom_left() const {
return pos + Vec2(0, size.y);
}
constexpr Vec2 bottom_right() const {
return pos + size;
}
constexpr Segment top() const {
return Segment(top_left(), top_right());
}
constexpr Segment bottom() const {
return Segment(bottom_left(), bottom_right());
}
constexpr Segment left() const {
return Segment(top_left(), bottom_left());
}
constexpr Segment right() const {
return Segment(top_right(), bottom_right());
}
constexpr Vec2 center() const {
return pos + size / 2;
}
constexpr LD area() const {
return size.x * size.y;
}
constexpr LD perimeter() const {
return (size.x + size.y) * 2;
}
constexpr bool contains(const Rect& r) const {
return sgn(left_x() - r.left_x()) <= 0 && sgn(r.right_x() - right_x()) <= 0 &&
sgn(top_y() - r.top_y()) <= 0 && sgn(r.bottom_y() - bottom_y()) <= 0;
}
constexpr bool contains(const Circle& c) const {
return sgn(left_x() - c.left_x()) <= 0 && sgn(c.right_x() - right_x()) <= 0 &&
sgn(top_y() - c.top_y()) <= 0 && sgn(c.bottom_y() - bottom_y()) <= 0;
}
friend std::ostream& operator<<(std::ostream& os, const Rect& r) {
return os << '(' << r.pos << ',' << r.size << ')';
}
friend std::istream& operator>>(std::istream& is, Rect& r) {
return is >> r.pos >> r.size;
}
};
} // namespace Geometric
#line 7 "Geometry/Triangle.hpp"
#include <cassert>
namespace Geometric {
struct Triangle {
Vec2 p1, p2, p3;
static LD area(LD a, LD b, LD c) {
LD s = (a + b + c) / 2;
return sqrt(s * (s - a) * (s - b) * (s - c));
}
Triangle() = default;
Triangle(const Vec2& _p1, const Vec2& _p2, const Vec2& _p3)
: p1(_p1), p2(_p2), p3(_p3) {
assert(abs(iSP(p1, p2, p3)) == 1);
}
std::tuple<LD, LD, LD> sides() const {
return {distance(p2, p3), distance(p1, p3), distance(p1, p2)};
}
LD area() const {
return abs((p1.x - p3.x) * (p2.y - p3.y) - (p2.x - p3.x) * (p1.y - p3.y)) / 2;
}
// 内接円
Circle incircle() const {
auto [l1, l2, l3] = sides();
LD s = l1 + l2 + l3;
LD x = (p1.x * l1 + p2.x * l2 + p3.x * l3) / s;
LD y = (p1.y * l1 + p2.y * l2 + p3.y * l3) / s;
s /= 2;
LD r = sqrt((s - l1) * (s - l2) * (s - l3) / s);
return Circle(x, y, r);
}
// 外接円
Circle cirnumscribed_circle() const {
Line l1((p1 + p2) / 2, (p1 + p2) / 2 + (p1 - p2).rotate270());
Line l2((p1 + p3) / 2, (p1 + p3) / 2 + (p1 - p3).rotate270());
Vec2 center = *cross_point(l1, l2);
return Circle(center, distance(center, p1));
}
friend std::ostream& operator<<(std::ostream& os, const Triangle& t) {
return os << '(' << t.p1 << ", " << t.p2 << ", " << t.p3 << ')';
}
friend std::istream& operator>>(std::istream& is, Triangle& t) {
return is >> t.p1 >> t.p2 >> t.p3;
}
};
} // namespace Geometric
#line 10 "Geometry/Polygon.hpp"
namespace Geometric {
struct Polygon : std::vector<Vec2> {
public:
Polygon() = default;
Polygon(std::size_t n) : std::vector<Vec2>(n) {}
Polygon(const std::vector<Vec2>& _p) : std::vector<Vec2>(_p) {}
LD area() const {
LD ans = 0;
for (std::size_t i = 0; i < size(); ++i) {
std::size_t next = i != size() - 1 ? i + 1 : 0;
ans += at(i).cross(at(next));
}
return std::abs(ans) / 2;
}
// 凸性判定（反時計回り）
bool is_convex() const {
if (size() < 3) {
return false;
}
for (std::size_t i = 0; i < size(); ++i) {
std::size_t prev = i != 0 ? i - 1 : size() - 1;
std::size_t next = i != size() - 1 ? i + 1 : 0;
if (iSP(at(prev), at(i), at(next)) == -1) {
return false;
}
}
return true;
}
// 凸包（反時計回り）
Polygon convex_hull() const {
std::vector<Vec2> ps = *this;
std::sort(ps.begin(), ps.end(), Vec2::compare_xy);
int n = ps.size(), k = 0;
Polygon result(2 * n);
for (int i = 0; i < n; result[k++] = ps[i++]) {
while (k >= 2 && iSP(result[k - 2], result[k - 1], ps[i]) <= 0) {
--k;
}
}
for (int i = n - 2, t = k + 1; i >= 0; result[k++] = ps[i--]) {
while (k >= t && iSP(result[k - 2], result[k - 1], ps[i]) <= 0) {
--k;
}
}
result.resize(k - 1);
return result;
}
// 凸包（一直線上の3点を含めない、反時計回り）
Polygon convex_hull_no_collinear() const {
std::vector<Vec2> ps = *this;
std::sort(ps.begin(), ps.end(), Vec2::compare_xy);
int n = ps.size(), k = 0;
Polygon result(2 * n);
for (int i = 0; i < n; result[k++] = ps[i++]) {
while (k >= 2 && iSP(result[k - 2], result[k - 1], ps[i]) != -1) {
--k;
}
}
for (int i = n - 2, t = k + 1; i >= 0; result[k++] = ps[i--]) {
while (k >= t && iSP(result[k - 2], result[k - 1], ps[i]) != -1) {
--k;
}
}
result.resize(k - 1);
return result;
}
// 直径
std::tuple<LD, std::size_t, std::size_t> diameter() const {
std::size_t i_start = 0, j_start = 0;
for (std::size_t i = 1; i < size(); ++i) {
if (at(i).y > at(i_start).y) i_start = i;
if (at(i).y < at(j_start).y) j_start = i;
}
LD max_dist = (at(i_start) - at(j_start)).length();
auto diff = [&](int i) {
return at((i + 1) % size()) - at(i);
};
std::size_t i = i_start, i_max = i_start;
std::size_t j = j_start, j_max = j_start;
do {
if (diff(i).cross(diff(j)) >= 0) {
j = (j + 1) % size();
} else {
i = (i + 1) % size();
}
if (LD d = (at(i) - at(j)).length(); max_dist < d) {
max_dist = d;
i_max = i;
j_max = j;
}
} while (i != i_start || j != j_start);
return {max_dist, i_max, j_max};
}
// 切断
Polygon cut(const Line& l) const {
Polygon result;
for (std::size_t i = 0; i < size(); ++i) {
Vec2 a = at(i), b = at(i != size() - 1 ? i + 1 : 0);
if (iSP(l.begin, l.end, a) != -1) {
result.push_back(a);
}
if (iSP(l.begin, l.end, a) * iSP(l.begin, l.end, b) < 0) {
result.push_back(*cross_point(Line(a, b), l));
}
}
return result;
}
friend std::ostream& operator<<(std::ostream& os, const Polygon& p) {
os << "{";
for (std::size_t i = 0; i < p.size(); ++i) {
if (i != 0) os << ", ";
os << p[i];
}
return os << "}";
}
friend std::istream& operator>>(std::istream& is, Polygon& p) {
for (auto& v : p) {
is >> v;
}
return is;
}
};
} // namespace Geometric
#line 13 "Geometry/Geometric.cpp"
namespace Geometric {
constexpr int sgn(LD a) {
return a < -EPS ? -1 : a > EPS ? 1 : 0;
}
constexpr LD deg_to_rad(LD deg) {
return deg * PI / 180;
}
constexpr LD rad_to_deg(LD rad) {
return rad * 180 / PI;
}
Vec2 Vec2::projection(const Line& l) const {
return l.begin +
l.vec().normalized() * (*this - l.begin).dot(l.vec()) / l.vec().length();
}
Vec2 Vec2::reflection(const Line& l) const {
return *this + (projection(l) - *this) * 2;
}
int iSP(const Vec2& a, const Vec2& b, const Vec2& c) {
int flag = sgn((b - a).cross(c - a));
if (flag != 0) {
return flag;
} else {
if (sgn((b - a).dot(c - b)) > 0) {
return 2;
} else if (sgn((a - b).dot(c - a)) > 0) {
return -2;
} else {
return 0;
}
}
}
int angle_type(const Vec2& a, const Vec2& b, const Vec2& c) {
if (int f = sgn((a - b).dot(c - b)); f > 0) {
return 0;
} else if (f == 0) {
return 1;
} else {
return 2;
}
}
LD angle(const Vec2& a, const Vec2& b, const Vec2& c) {
// return acos((a - b).dot(c - b) / (distance(a, b) * distance(c, b)));
// return std::abs((a - b).rotation(-(c - b).angle()).angle());
return (c - b).rotation(-(a - b).angle()).angle();
}
LD distance(const Vec2& v1, const Vec2& v2) {
return std::hypot(v1.x - v2.x, v1.y - v2.y);
}
LD distance(const Vec2& v, const Line& l) {
return std::abs(l.vec().cross(v - l.begin) / l.vec().length());
}
LD distance(const Vec2& v, const Segment& s) {
if (sgn(s.vec().dot(v - s.begin)) < 0 || sgn(s.counter_vec().dot(v - s.end)) < 0) {
return std::min(distance(v, s.begin), distance(v, s.end));
} else {
return distance(Line(s), v);
}
}
LD distance(const Vec2& v, const Circle& c) {
return std::max<LD>(0, distance(c.center, v) - c.r);
}
LD distance(const Line& l, const Vec2& v) {
return distance(v, l);
}
LD distance(const Line& l1, const Line& l2) {
return l1.is_parallel(l2) ? distance(l1, l2.begin) : 0;
}
LD distance(const Segment& s, const Vec2& v) {
return distance(v, s);
}
LD distance(const Segment& s1, const Segment& s2) {
if (intersect(s1, s2)) {
return 0;
} else {
return std::min({distance(s1, s2.begin), distance(s1, s2.end),
distance(s1.begin, s2), distance(s1.end, s2)});
}
}
LD distance(const Circle& c, const Vec2& v) {
return distance(v, c);
}
LD distance(const Circle& c1, const Circle& c2) {
return std::max<LD>(0, distance(c1.center, c2.center) - (c1.r + c2.r));
}
bool intersect(const Vec2& v1, const Vec2& v2) {
return v1 == v2;
}
bool intersect(const Vec2& v, const Line& l) {
return std::abs(iSP(v, l.begin, l.end)) != 1;
}
bool intersect(const Vec2& v, const Segment& l) {
return iSP(l.begin, l.end, v) == 0;
}
bool intersect(const Vec2& v, const Circle& c) {
return sgn(distance(c.center, v) - c.r) <= 0;
}
bool intersect(const Vec2& v, const Rect& r) {
return sgn(r.left_x() - v.x) <= 0 && sgn(v.x - r.right_x()) &&
sgn(r.top_y() - v.y) <= 0 && sgn(v.y - r.bottom_y());
}
bool intersect(const Vec2& v, const Polygon& p) {
LD theta = 0;
for (std::size_t i = 0; i < p.size(); ++i) {
Vec2 next = p[i != p.size() - 1 ? i + 1 : 0];
if (intersect(Segment(p[i], next), v)) {
return true;
}
theta += angle(p[i], v, next);
}
return std::abs(theta) > 1;
}
bool intersect(const Line& l, const Vec2& v) {
return intersect(v, l);
}
bool intersect(const Line& l1, const Line& l2) {
return !l1.is_parallel(l2);
}
bool intersect(const Line& l, const Circle& c) {
return sgn(distance(c.center, l) - c.r) <= 0;
}
bool intersect(const Segment& l, const Vec2& v) {
return intersect(v, l);
}
bool intersect(const Segment& s1, const Segment& s2) {
return iSP(s1.begin, s1.end, s2.begin) * iSP(s1.begin, s1.end, s2.end) <= 0 &&
iSP(s2.begin, s2.end, s1.begin) * iSP(s2.begin, s2.end, s1.end) <= 0;
}
bool intersect(const Segment& s, const Circle& c) {
return sgn(distance(c.center, s) - c.r) <= 0;
}
bool intersect(const Circle& c, const Vec2& v) {
return intersect(v, c);
}
bool intersect(const Circle& c, const Line& l) {
return intersect(l, c);
}
bool intersect(const Circle& c, const Segment& s) {
return intersect(s, c);
}
bool intersect(const Circle& c1, const Circle& c2) {
return sgn(distance(c1.center, c2.center) - (c1.r + c2.r)) <= 0;
}
bool intersect(const Circle& c, const Rect& r) {
return intersect(Rect(r.pos - Vec2(0, c.r), r.size + Vec2(0, c.r * 2)), c.center) ||
intersect(Rect(r.pos - Vec2(c.r, 0), r.size + Vec2(c.r * 2, 0)), c.center) ||
intersect(c, r.top_left()) || intersect(c, r.top_right()) ||
intersect(c, r.bottom_left()) || intersect(c, r.bottom_right());
}
bool intersect(const Rect& r, const Vec2& v) {
return intersect(v, r);
}
bool intersect(const Rect& r1, const Rect& r2) {
return sgn(std::max(r1.left_x(), r2.left_x()) -
std::min(r1.right_x(), r2.right_x())) <= 0 &&
sgn(std::max(r1.top_y(), r2.top_y()) - std::min(r1.bottom_y(), r2.bottom_y())) <=
0;
}
bool intersect(const Rect& r, const Circle& c) {
return intersect(c, r);
}
bool intersect(const Polygon& p, const Vec2& v) {
return intersect(v, p);
}
bool tangent(const Vec2& v1, const Vec2& v2) {
return intersect(v1, v2);
}
bool tangent(const Vec2& v, const Line& l) {
return intersect(v, l);
}
bool tangent(const Vec2& v, const Segment& l) {
return intersect(v, l);
}
bool tangent(const Vec2& v, const Circle& c) {
return sgn(distance(v, c.center) - c.r) == 0;
}
bool tangent(const Vec2& v, const Rect& r) {
return tangent(r.top(), v) || tangent(r.bottom(), v) || tangent(r.left(), v) ||
tangent(r.right(), v);
}
bool tangent(const Vec2& v, const Polygon& p) {
for (std::size_t i = 0; i < p.size(); ++i) {
if (tangent(Segment(p[i], p[(i + 1) % p.size()]), v)) {
return true;
}
}
return false;
}
bool tangent(const Line& l, const Vec2& v) {
return tangent(v, l);
}
bool tangent(const Line& l, const Circle& c) {
return sgn(distance(c.center, l) - c.r) == 0;
}
bool tangent(const Line& l, const Rect& r) {
bool f1 = tangent(r.top_left(), l), f2 = tangent(r.top_right(), l),
f3 = tangent(r.bottom_right(), l), f4 = tangent(r.bottom_left(), l);
return f1 + f2 + f3 + f4 == 1 || (f1 && f2) || (f2 && f3) || (f3 && f4) || (f4 && f1);
}
bool tangent(const Segment& l, const Vec2& v) {
return tangent(v, l);
}
bool tangent(const Circle& c, const Vec2& v) {
return tangent(v, c);
}
bool tangent(const Circle& c, const Line& l) {
return tangent(l, c);
}
bool tangent(const Circle& c1, const Circle& c2) {
LD l1 = distance(c1.center, c2.center), l2 = c1.r, l3 = c2.r;
return sgn(l1 + l2 + l3 - std::max({l1, l2, l3}) * 2) == 0;
}
bool tangent(const Rect& r, const Vec2& v) {
return tangent(v, r);
}
bool tangent(const Rect& r, const Line& l) {
return tangent(l, r);
}
bool tangent(const Polygon& p, const Vec2& v) {
return tangent(v, p);
}
std::optional<Vec2> cross_point(const Line& l1, const Line& l2) {
if (intersect(l1, l2)) {
// return begin + vec() * std::abs((l.end - begin).cross(l.vec()) /
// vec().cross(l.vec()));
auto [a, b, c] = l1.abc();
auto [A, B, C] = l2.abc();
LD d = A * b - a * B;
return Vec2((B * c - b * C) / d, (a * C - A * c) / d);
} else {
return std::nullopt;
}
}
std::optional<Vec2> cross_point(const Segment& s1, const Segment& s2) {
if (intersect(s1, s2)) {
return cross_point(Line(s1), Line(s2));
} else {
return std::nullopt;
}
}
std::vector<Vec2> cross_points(const Line& l, const Circle& c) {
LD dist = distance(l, c.center);
if (int f = sgn(c.r - dist); f == 1) {
LD x = std::sqrt(c.r * c.r - dist * dist);
Vec2 p = c.center.projection(l);
return {p + l.vec().normalized() * x, p + l.counter_vec().normalized() * x};
} else if (f == 0) {
return {c.center.projection(l)};
} else {
return {};
}
}
std::vector<Vec2> cross_points(const Segment& s, const Circle& c) {
std::vector<Vec2> result;
for (const Vec2& v : cross_points(Line(s), c)) {
if (intersect(v, s)) {
result.push_back(v);
}
}
return result;
}
std::vector<Vec2> cross_points(const Circle& c, const Line& l) {
return cross_points(l, c);
}
std::vector<Vec2> cross_points(const Circle& c, const Segment& s) {
return cross_points(s, c);
}
std::vector<Vec2> cross_points(const Circle& c1, const Circle& c2) {
Vec2 vec = (c1.center - c2.center).normalized(); // c2 -> c1
LD dist = distance(c1.center, c2.center);
if (sgn(dist - c1.r - c2.r) == 0) {
return {c2.center + vec * c2.r};
} else if (sgn(c1.r + dist - c2.r) == 0) {
return {c1.center + vec * c1.r};
} else if (sgn(c2.r + dist - c1.r) == 0) {
return {c2.center + vec.rotate180() * c2.r};
} else if (intersect(c1, c2)) {
LD area = Triangle::area(dist, c1.r, c2.r);
LD y = 2 * area / dist, x = std::sqrt(c1.r * c1.r - y * y);
LD r1_s = c1.r * c1.r, r2_s = c2.r * c2.r, dist_s = dist * dist;
Vec2 h = c1.center + vec * (r2_s < r1_s + dist_s ? -x : x),
v2 = vec.rotate90() * y;
return {h + v2, h - v2};
} else {
return {};
}
}
std::vector<Vec2> tangent_to_circle(const Circle& c, const Vec2& v) {
LD dist = distance(c.center, v);
if (sgn(dist - c.r) >= 0) {
LD x = std::sqrt(dist * dist - c.r * c.r);
return cross_points(Circle(v, x), c);
} else {
return {};
}
}
} // namespace Geometric
#line 10 "test/Geometric_cross_points_between_line_and_circle.test.cpp"
using namespace std;
int main() {
Geometric::Circle c;
cin >> c;
int q;
cin >> q;
while (q--) {
Geometric::Line l;
cin >> l;
auto ans = cross_points(c, l);
assert(1 <= ans.size() && ans.size() <= 2);
if (ans.size() == 1) {
ans.push_back(ans[0]);
} else {
sort(ans.begin(), ans.end(), Geometric::Vec2::compare_xy);
}
printf("%.12Lf %.12Lf %.12Lf %.12Lf\n", ans[0].x, ans[0].y, ans[1].x, ans[1].y);
}
}