verify/geometry/igor-tests/10.cpp

• View this file on GitHub
• Last update: 2024-08-09 22:59:12+00:00
• Link: https://ejudge.algocode.ru/cgi-bin/new-client?contest_id=55063

Depends on

• contest/template.cpp
• geometry/Line.cpp
• geometry/Point.cpp
• geometry/Tangents.cpp

Verified with

• verify/geometry/igor-tests/include-all.test.cpp

Code

// Yandex Algo 2023-2024. C. Геометрия 2 A - Касательные к окружности
// https://ejudge.algocode.ru/cgi-bin/new-client?contest_id=55063
#define main main228
#include "../../../contest/template.cpp"
#undef main

#include "../../../geometry/Point.cpp"
#include "../../../geometry/Line.cpp"
#include "../../../geometry/Tangents.cpp"


signed main() {
    cin.tie(0)->sync_with_stdio(0);
    cout.precision(20), cout.setf(ios::fixed);
    point o, p;
    ld r;
    cin >> o.x >> o.y >> r >> p.x >> p.y;
    point I1, I2;
    int ans = tangents(o, r, p, I1, I2);
    if (!ans) {
      cout << ans << endl;
    } else if (ans == 1) {
      cout << ans << "\n" << I1.x << " " << I1.y << endl;
    } else if (ans == 2) {
      cout << ans << "\n" << I1.x << " " << I1.y << "\n" << I2.x << " " << I2.y << endl;
    }
}

#line 1 "verify/geometry/igor-tests/10.cpp"
// Yandex Algo 2023-2024. C. Геометрия 2 A - Касательные к окружности
// https://ejudge.algocode.ru/cgi-bin/new-client?contest_id=55063
#define main main228
#line 1 "contest/template.cpp"
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
using ull = unsigned long long;

#define pbc push_back
#define mp make_pair
#define all(v) (v).begin(), (v).end()
#define vin(v) for (auto &el : a) cin >> el

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

template <typename T1, typename T2> inline void chkmin(T1 &x, const T2 &y) {
    if (y < x) {
        x = y;
    }
}

template <typename T1, typename T2> inline void chkmax(T1 &x, const T2 &y) {
    if (x < y) {
        x = y;
    }
}

void solve() {
    
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    cout.precision(20), cout.setf(ios::fixed);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}
#line 5 "verify/geometry/igor-tests/10.cpp"
#undef main

#line 1 "geometry/Point.cpp"
/**
 * Author: alexxela12345,daubi,talant
 * Date: 2024-08-03
 * Description: struct Point
 */

const ld EPS = 1e-7;

ld sq(ld x) {
    return x * x;
}

int sign(ld x) {
    if (x < -EPS) {
        return -1;
    }
    if (x > EPS) {
        return 1;
    }
    return 0;
}

#define vec point
struct point {//% - cross, * - dot
    ld x, y;
    auto operator<=>(const point&) const = default;
};
ld operator*(const point &a, const point &b) {
    return a.x * b.x + a.y * b.y;
}
ld operator%(const point &a, const point &b) {
    return a.x * b.y - a.y * b.x;
}
point operator-(const point &a, const point &b) {
    return {a.x - b.x, a.y - b.y};
}
point operator+(const point &a, const point &b) {
    return {a.x + b.x, a.y + b.y};
}
point operator*(const point &a, ld b) {
    return {a.x * b, a.y * b};
}
point operator/(const point &a, ld b) {
    return {a.x / b, a.y / b};
}
bool operator<(const point &a, const point &b)  {
    if (sign(a.y - b.y) != 0) {
        return a.y < b.y;
    } else if (sign(a.x - b.x) != 0) {
        return a.x < b.x;
    }
    return 0;
}
ld len2(const point &a) {
    return sq(a.x) + sq(a.y);
}
ld len(const point &a) {
    return sqrt(len2(a));
}
point norm(point a) {
    return a / len(a);
}
int half(point a) {
    return (sign(a.y) == -1 || (sign(a.y) ==0 && a.x < 0));
}
point ort(point a) {
    return {-a.y, a.x};
}
point turn(point a, ld ang) {
    return {a.x * cos(ang) - a.y * sin(ang), a.x * sin(ang) + a.y * cos(ang)};
}
ld getAngle(point &a, point &b) {
    return atan2(a % b, a * b);
}
bool cmpHalf(const point &a, const point &b) {
    if (half(a) != half(b)) {
        return half(b);
    } else {
        int sgn = sign(a % b);
        if (!sgn) {
            return len2(a) < len2(b);
        } else {
            return sgn == 1;
        }
    }
}
#line 1 "geometry/Line.cpp"
/**
 * Author: alexxela12345,daubi,talant
 * Date: 2024-08-03
 * Description: struct Line
 */

struct line {
    ld a, b, c;
    void norm() {
        // for half planes
        ld d = len({a, b});
        assert(sign(d) > 0);
        a /= d;
        b /= d;
        c /= d;
    }
    ld eval(point p) const { return a * p.x + b * p.y + c; }
    bool isIn(point p) const { return sign(eval(p)) >= 0; }
    bool operator==(const line &other) const {
        return sign(a * other.b - b * other.a) == 0 &&
               sign(a * other.c - c * other.a) == 0 &&
               sign(b * other.c - c * other.b) == 0;
    }
};
line getln(point a, point b) {
    line res;
    res.a = a.y - b.y;
    res.b = b.x - a.x;
    res.c = -(res.a * a.x + res.b * a.y);
    res.norm();
    return res;
}
#line 1 "geometry/Tangents.cpp"
/**
 * Author: Igor Markelov
 * Date: 2022-11-18
 * Description: Tangents to circles.
 */
// tangents from point to circle
int tangents(point &o, ld r, point &p, point &i1, point &i2) {
    ld ln = len(o - p);
    int sgn = sign(ln - r);
    if (sgn == -1) {
        return 0;
    } else if (sgn == 0) {
        i1 = p;
        return 1;
    } else {
        ld x = sq(r) / ln;
        vec v = norm(p - o) * x;
        point a = o + v;
        v = ort(norm(p - o)) * sqrt(sq(r) - sq(x));
        i1 = a + v;
        i2 = a - v;
        return 2;
    }
}

void _tangents(point c, ld r1, ld r2, vector<line> &ans) {
    ld r = r2 - r1;
    ld z = sq(c.x) + sq(c.y);
    ld d = z - sq(r);
    if (sign(d) == -1)
        return;
    d = sqrt(abs(d));
    line l;
    l.a = (c.x * r + c.y * d) / z;
    l.b = (c.y * r - c.x * d) / z;
    l.c = r1;
    ans.push_back(l);
}
// tangents between two circles
vector<line> tangents(point o1, ld r1, point o2, ld r2) {
    vector<line> ans;
    for (int i = -1; i <= 1; i += 2)
        for (int j = -1; j <= 1; j += 2)
            _tangents(o2 - o1, r1 * i, r2 * j, ans);
    for (int i = 0; i < (int)ans.size(); ++i)
        ans[i].c -= ans[i].a * o1.x + ans[i].b * o1.y;
    return ans;
}
#line 10 "verify/geometry/igor-tests/10.cpp"


signed main() {
    cin.tie(0)->sync_with_stdio(0);
    cout.precision(20), cout.setf(ios::fixed);
    point o, p;
    ld r;
    cin >> o.x >> o.y >> r >> p.x >> p.y;
    point I1, I2;
    int ans = tangents(o, r, p, I1, I2);
    if (!ans) {
      cout << ans << endl;
    } else if (ans == 1) {
      cout << ans << "\n" << I1.x << " " << I1.y << endl;
    } else if (ans == 2) {
      cout << ans << "\n" << I1.x << " " << I1.y << "\n" << I2.x << " " << I2.y << endl;
    }
}

Back to top page