verify/aizu_online_judge/cgl/cross_points_of_a_circle_and_a_line.test.cpp

• View this file on GitHub
• Last update: 2024-11-09 01:34:39+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/4/CGL/7/CGL_7_D

Depends on

• circle_2d (src/geometry/circle_2d.hpp)
• line_and_segment_2d (src/geometry/line_and_segment_2d.hpp)
• point_2d (src/geometry/point_2d.hpp)
• template (src/geometry/template.hpp)
• template (src/template/template.hpp)

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/4/CGL/7/CGL_7_D"
#define ERROR 0.000001
#include "../../../src/template/template.hpp"
#include "../../../src/geometry/template.hpp"
#include "../../../src/geometry/point_2d.hpp"
#include "../../../src/geometry/line_and_segment_2d.hpp"
#include "../../../src/geometry/circle_2d.hpp"
int main(void) {
    Circle c;
    cin >> c.p >> c.r;
    int q;
    cin >> q;
    while(q--) {
        Point p1, p2;
        cin >> p1 >> p2;
        Line l = Line(p1, p2);
        auto cross_point = intersection_cl(c, l);
        assert(int(cross_point.size()) == 1 or int(cross_point.size()) == 2);
        if(int(cross_point.size()) == 1) cross_point.push_back(cross_point[0]);
        sort(cross_point.begin(), cross_point.end(), comp_x);
        cout << cross_point[0] << ' ' << cross_point[1] << '\n';
    }
}

#line 1 "verify/aizu_online_judge/cgl/cross_points_of_a_circle_and_a_line.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/4/CGL/7/CGL_7_D"
#define ERROR 0.000001
#line 2 "src/template/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<long long, long long>;
#define rep(i, a, b) for(long long i = (a); i < (b); ++i)
#define rrep(i, a, b) for(long long i = (a); i >= (b); --i)
constexpr long long inf = 4e18;
struct SetupIO {
    SetupIO() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout << fixed << setprecision(30);
    }
} setup_io;
#line 3 "src/geometry/template.hpp"
using Real = long double;
constexpr Real EPS = Real(1e-8), PI = 3.141592653589793238462643383279L;
int sign(const Real& r) {
    if(r <= -EPS) return -1;
    if(r >= +EPS) return +1;
    return 0;
}
bool eq(const Real& a, const Real& b) {
    return sign(a - b) == 0;
}
#line 4 "src/geometry/point_2d.hpp"
using Point = complex<Real>;
istream& operator>>(istream& is, Point& p) {
    Real a, b;
    is >> a >> b;
    p = Point(a, b);
    return is;
}
ostream& operator<<(ostream& os, const Point& p) {
    return os << p.real() << " " << p.imag();
}
Point operator*(const Point& p, const Real& d) {
    return Point(p.real() * d, p.imag() * d);
}
Point operator/(const Point& p, const Real& d) {
    return Point(p.real() / d, p.imag() / d);
}
Point rot(const Point& p, const Real& theta) {
    return p * Point(cos(theta), sin(theta));
}
Real dot(const Point& p1, const Point& p2) {
    return (conj(p1) * p2).real();
}
Real cross(const Point& p1, const Point& p2) {
    return (conj(p1) * p2).imag();
}
Real dist(const Point& p1, const Point& p2) {
    return abs(p1 - p2);
}
bool comp_x(const Point& p1, const Point& p2) {
    return eq(p1.real(), p2.real()) ? p1.imag() < p2.imag() : p1.real() < p2.real();
}
bool comp_y(const Point& p1, const Point& p2) {
    return eq(p1.imag(), p2.imag()) ? p1.real() < p2.real() : p1.imag() < p2.imag();
}
bool comp_arg(const Point& p1, const Point& p2) {
    return arg(p1) < arg(p2);
}
int ccw(const Point& a, Point b, Point c) {
    b -= a;
    c -= a;
    if(sign(cross(b, c)) == 1) return 1;
    if(sign(cross(b, c)) == -1) return -1;
    if(sign(dot(b, c)) == -1) return +2;
    if(norm(b) < norm(c)) return -2;
    return 0;
}
Real closest_pair(vector<Point> ps) {
    if((int)ps.size() <= 1) return Real(1e18);
    sort(ps.begin(), ps.end(), comp_x);
    vector<Point> memo(ps.size());
    auto func = [&](const auto& func, const int l, const int r) -> Real {
        if(r - l <= 1) return Real(1e18);
        const int m = (l + r) >> 1;
        const Real x = ps[m].real();
        Real res = min(func(func, l, m), func(func, m, r));
        inplace_merge(ps.begin() + l, ps.begin() + m, ps.begin() + r, comp_y);
        int cnt = 0;
        for(int i = l; i < r; ++i) {
            if(abs(ps[i].real() - x) >= res) continue;
            for(int j = 0; j < cnt; ++j) {
                const Point d = ps[i] - memo[cnt - j - 1];
                if(d.imag() >= res) break;
                res = min(res, abs(d));
            }
            memo[cnt++] = ps[i];
        }
        return res;
    };
    return func(func, 0, (int)ps.size());
}
#line 5 "src/geometry/line_and_segment_2d.hpp"
struct Line {
    Point a, b;
    Line() = default;
    Line(const Point& a, const Point& b)
        : a(a), b(b) {}
};
using Segment = Line;
bool is_parallel(const Line& a, const Line& b) {
    return eq(cross(a.b - a.a, b.b - b.a), 0.0);
}
bool is_orthogonal(const Line& a, const Line& b) {
    return eq(dot(a.b - a.a, b.b - b.a), 0.0);
}
Point projection(const Line& l, const Point& p) {
    Real t = dot(p - l.a, l.b - l.a) / norm(l.b - l.a);
    return l.a + (l.b - l.a) * t;
}
Point reflection(const Line& l, const Point& p) {
    return p + (projection(l, p) - p) * 2.0;
}
bool is_intersect_lp(const Line& l, const Point& p) {
    return abs(ccw(l.a, l.b, p)) != 1;
}
bool is_intersect_sp(const Segment& s, const Point& p) {
    return ccw(s.a, s.b, p) == 0;
}
bool is_intersect_ll(const Line& l1, const Line& l2) {
    if(!eq(cross(l1.b - l1.a, l2.b - l2.a), 0.0)) return true;
    return eq(cross(l1.b - l1.a, l2.b - l1.a), 0.0);
}
bool is_intersect_ls(const Line& l, const Segment& s) {
    return sign(cross(l.b - l.a, s.a - l.a) * cross(l.b - l.a, s.b - l.a)) <= 0;
}
bool is_intersect_sl(const Segment& s, const Line& l) {
    return is_intersect_ls(l, s);
}
bool is_intersect_ss(const Segment& s1, const Segment& s2) {
    if(ccw(s1.a, s1.b, s2.a) * ccw(s1.a, s1.b, s2.b) > 0) return false;
    return ccw(s2.a, s2.b, s1.a) * ccw(s2.a, s2.b, s1.b) <= 0;
}
vector<Point> intersection_ll(const Line& l1, const Line& l2) {
    vector<Point> res;
    if(!is_intersect_ll(l1, l2)) return res;
    Real a = cross(l1.b - l1.a, l2.b - l2.a);
    Real b = cross(l1.b - l1.a, l1.b - l2.a);
    if(eq(a, 0.0) and eq(b, 0.0)) {
        res.emplace_back(l2.a);
    } else {
        res.emplace_back(l2.a + (l2.b - l2.a) * b / a);
    }
    return res;
}
vector<Point> intersection_ss(const Segment& s1, const Segment& s2) {
    return is_intersect_ss(s1, s2) ? intersection_ll(Line(s1), Line(s2)) : vector<Point>();
}
Real dist_lp(const Line& l, const Point& p) {
    return abs(p - projection(l, p));
}
Real dist_sp(const Segment& s, const Point& p) {
    const Point h = projection(s, p);
    if(is_intersect_sp(s, h)) return abs(h - p);
    return min(abs(s.a - p), abs(s.b - p));
}
Real dist_ll(const Line& l1, const Line& l2) {
    if(is_intersect_ll(l1, l2)) return 0.0;
    return dist_lp(l1, l2.a);
}
Real dist_ss(const Segment& s1, const Segment& s2) {
    if(is_intersect_ss(s1, s2)) return 0.0;
    return min({dist_sp(s1, s2.a), dist_sp(s1, s2.b), dist_sp(s2, s1.a), dist_sp(s2, s1.b)});
}
Real dist_ls(const Line& l, const Segment& s) {
    if(is_intersect_ls(l, s)) return 0.0;
    return min(dist_lp(l, s.a), dist_lp(l, s.b));
}
Real dist_sl(const Segment& s, const Line& l) {
    return dist_ls(l, s);
}
#line 6 "src/geometry/circle_2d.hpp"
struct Circle {
    Point p;
    Real r;
    Circle() = default;
    Circle(const Point& p, const Real& r)
        : p(p), r(r) {}
};
bool is_intersect_cp(const Circle& c, const Point& p) {
    return eq(abs(p - c.p), c.r);
}
bool is_intersect_cl(const Circle& c, const Line& l) {
    return sign(c.r - dist_lp(l, c.p)) >= 0;
}
int is_intersect_cc(Circle c1, Circle c2) {
    if(c1.r < c2.r) swap(c1, c2);
    const Real d = abs(c1.p - c2.p);
    const int a = sign(d - c1.r - c2.r);
    if(a >= 0) return a + 3;
    return sign(d - c1.r + c2.r) + 1;
}
vector<Point> intersection_cl(const Circle& c, const Line& l) {
    const Point h = projection(l, c.p);
    const Point e = (l.b - l.a) / abs(l.b - l.a);
    vector<Point> res;
    if(!is_intersect_cl(c, l)) return res;
    if(eq(dist_lp(l, c.p), c.r)) {
        res.emplace_back(h);
    } else {
        const Real b = sqrt(c.r * c.r - norm(h - c.p));
        res.emplace_back(h - e * b);
        res.emplace_back(h + e * b);
    }
    return res;
}
vector<Point> intersection_cs(const Circle& c, const Segment& s) {
    const vector<Point> cand = intersection_cl(c, Line(s));
    vector<Point> res;
    for(const Point& p : cand) {
        if(ccw(s.a, s.b, p) == 0) {
            res.emplace_back(p);
        }
    }
    return res;
}
vector<Point> intersection_cc(const Circle& c1, const Circle& c2) {
    const Real d = abs(c1.p - c2.p);
    const Real a = acos((c1.r * c1.r + d * d - c2.r * c2.r) / (Real(2.0) * c1.r * d));
    const Real t = atan2(c2.p.imag() - c1.p.imag(), c2.p.real() - c1.p.real());
    vector<Point> res;
    if(is_intersect_cc(c1, c2) % 4 == 0) return res;
    if(eq(a, 0.0)) {
        res.emplace_back(c1.p + rot(Point(c1.r, 0.0), t));
    } else {
        res.emplace_back(c1.p + rot(Point(c1.r, 0.0), t + a));
        res.emplace_back(c1.p + rot(Point(c1.r, 0.0), t - a));
    }
    return res;
}
vector<Point> tangent_cp(const Circle& c, const Point& p) {
    return intersection_cc(c, Circle(p, sqrt(norm(p - c.p) - c.r * c.r)));
}
vector<Line> tangent_cc(Circle c1, Circle c2) {
    vector<Line> res;
    if(c1.r < c2.r) swap(c1, c2);
    const Real r = abs(c2.p - c1.p);
    if(eq(r, 0.0)) return res;
    const Point u = (c2.p - c1.p) / r;
    const Point v = rot(u, PI * 0.5);
    for(const Real s : {Real(1.0), Real(-1.0)}) {
        const Real h = (c1.r + c2.r * s) / r;
        if(eq(abs(h), Real(1.0))) {
            res.emplace_back(c1.p + u * c1.r, c1.p + (u + v) * c1.r);
        } else if(abs(h) < Real(1.0)) {
            const Point uu = u * h, vv = v * sqrt(Real(1.0) - h * h);
            res.emplace_back(c1.p + (uu + vv) * c1.r, c2.p - (uu + vv) * c2.r * s);
            res.emplace_back(c1.p + (uu - vv) * c1.r, c2.p - (uu - vv) * c2.r * s);
        }
    }
    return res;
}
Circle inscribed_circle(const Point& a, const Point& b, const Point& c) {
    const Real A = abs(b - c), B = abs(c - a), C = abs(a - b);
    const Point x = Point((a * A + b * B + c * C) / (A + B + C));
    const Real r = dist_sp(Segment(a, b), x);
    return Circle(x, r);
}
Circle circumscribed_circle(const Point& a, const Point& b, const Point& c) {
    const Point m1((a + b) / 2.0), m2((b + c) / 2.0);
    const Point v((b - a).imag(), (a - b).real()), w((b - c).imag(), (c - b).real());
    const Line s(m1, Point(m1 + v)), t(m2, Point(m2 + w));
    const Point x = intersection_ll(s, t)[0];
    return Circle(x, abs(a - x));
}
Circle appollonius(const Point& p1, const Point& p2, const Real& a, const Real& b) {
    const Point q1 = (p1 * b + p2 * a) / (a + b), q2 = (-p1 * b + p2 * a) / (a - b);
    return Circle((q1 + q2) * 0.5, abs(q1 - q2) * 0.5);
}
Real area_cc(const Circle& c1, const Circle& c2) {
    const Real d = abs(c1.p - c2.p);
    if(c1.r + c2.r <= d + EPS) return 0.0;
    if(d <= abs(c1.r - c2.r) + EPS) {
        const Real r = min(c1.r, c2.r);
        return r * r * PI;
    }
    const Real rc = (d * d + c1.r * c1.r - c2.r * c2.r) / (Real(2.0) * d);
    const Real theta = acos(rc / c1.r);
    const Real phi = acos((d - rc) / c2.r);
    return c1.r * c1.r * theta + c2.r * c2.r * phi - d * c1.r * sin(theta);
}
Real area_pc(const vector<Point>& ps, const Circle& c) {
    auto calc_element = [&](const Point& a, const Point& b, const Real& r, const bool triangle) -> Real {
        if(triangle) return cross(a, b) / 2.0;
        const Point tmp = b * Point(a.real(), -a.imag());
        const Real ang = atan2(tmp.imag(), tmp.real());
        return r * r * ang / 2.0;
    };
    auto cross_area = [&](const Circle& c, const Point& ia, const Point& ib) -> Real {
        const Point a = ia - c.p, b = ib - c.p;
        if(abs(a - b) < EPS) return 0;
        const bool isin_a = (abs(a) < c.r + EPS);
        const bool isin_b = (abs(b) < c.r + EPS);
        if(isin_a and isin_b) return calc_element(a, b, c.r, true);
        const Circle oc(Point(0.0, 0.0), c.r);
        const Segment seg(a, b);
        const vector<Point> cr = intersection_cs(oc, seg);
        if(cr.empty()) return calc_element(a, b, c.r, false);
        const Point s = cr[0], t = cr.back();
        return calc_element(s, t, c.r, true) + calc_element(a, s, c.r, isin_a) + calc_element(t, b, c.r, isin_b);
    };
    const int n = (int)ps.size();
    if(n < 3) return 0.0;
    Real S = 0;
    for(int i = 0; i < n; ++i) {
        S += cross_area(c, ps[i], ps[(i + 1) % n]);
    }
    return S;
}
#line 8 "verify/aizu_online_judge/cgl/cross_points_of_a_circle_and_a_line.test.cpp"
int main(void) {
    Circle c;
    cin >> c.p >> c.r;
    int q;
    cin >> q;
    while(q--) {
        Point p1, p2;
        cin >> p1 >> p2;
        Line l = Line(p1, p2);
        auto cross_point = intersection_cl(c, l);
        assert(int(cross_point.size()) == 1 or int(cross_point.size()) == 2);
        if(int(cross_point.size()) == 1) cross_point.push_back(cross_point[0]);
        sort(cross_point.begin(), cross_point.end(), comp_x);
        cout << cross_point[0] << ' ' << cross_point[1] << '\n';
    }
}

Back to top page