結果

問題 No.3344 Common Tangent Line
コンテスト
ユーザー abc864197532
提出日時 2025-11-14 00:04:27
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 396 ms / 3,000 ms
コード長 3,618 bytes
コンパイル時間 3,350 ms
コンパイル使用メモリ 285,784 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-11-14 00:05:19
合計ジャッジ時間 24,385 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define all(a) a.begin(), a.end()
#define sz(a) ((int)a.size())
#define pb push_back
#ifdef Doludu
template <typename T>
ostream& operator << (ostream &o, vector<T> vec) {
    o << "{"; int f = 0;
    for (T i : vec) o << (f++ ? " " : "") << i;
    return o << "}";
}
void bug__(int c, auto ...a) {
    cerr << "\e[1;" << c << "m";
    (..., (cerr << a << " "));
    cerr << "\e[0m" << endl;
}
#define bug_(c, x...) bug__(c, __LINE__, "[" + string(#x) + "]", x)
#define bug(x...) bug_(32, x)
#define bugv(x...) bug_(36, vector(x))
#define safe bug_(33, "safe")
#else
#define bug(x...) void(0)
#define bugv(x...) void(0)
#define safe void(0)
#endif
const int mod = 998244353, N = 200087;

const double eps = 1e-8, PI = acos(-1);
int sign(double x)
{ return fabs(x) <= eps ? 0 : (x > 0 ? 1 : -1); }
double normalize(double x) {
  while (x < -eps) x += PI * 2;
  while (x > PI * 2 + eps) x -= PI * 2;
  return x; }
template <typename T> struct P {
  T x, y;
  P (T _x = 0, T _y = 0) : x(_x), y(_y) {}
  P<T> operator + (P<T> o) {
    return P<T>(x + o.x, y + o.y);}
  P<T> operator - (P<T> o) {
    return P<T>(x - o.x, y - o.y);}
  P<T> operator * (T k) {return P<T>(x * k, y * k);}
  P<T> operator / (T k) {return P<T>(x / k, y / k);}
  T operator * (P<T> o) {return x * o.x + y * o.y;}
  T operator ^ (P<T> o) {return x * o.y - y * o.x;}
  friend ostream& operator << (ostream &o, P<T> a) {
    return o << "(" << a.x << ", " << a.y << ")"; }
  bool operator == (P<T> o) {
    return sign(x - o.x) == 0 && sign(y - o.y) == 0;}
};
using Pt = P<double>;
struct Line { Pt a, b; };
struct Cir { Pt o; double r; };
double abs2(Pt a) { return a * a; }
double abs(Pt a) { return sqrt(abs2(a)); }
double theta(Pt a)
{ return normalize(atan2(a.y, a.x)); }
Pt unit(Pt o) { return o / abs(o); }
Pt rot(Pt a, double o) // CCW
{ double c = cos(o), s = sin(o);
  return Pt(c * a.x - s * a.y, s * a.x + c * a.y); }
Pt proj_vec(Pt a, Pt b, Pt c) // vector ac proj to ab
{return (b - a) * ((c - a) * (b - a)) / (abs2(b - a));}
Pt proj_pt(Pt a, Pt b, Pt c) // point c proj to ab
{ return proj_vec(a, b, c) + a; }
Pt perp(Pt o) { return Pt(-o.y, o.x); }

auto circles_tangent(Cir c1, Cir c2, int sign1) {
  // sign1 = 1 for outer tang, -1 for inter tang
  vector<Line> res;
  double d_sq = abs2(c1.o - c2.o);
  if (sign(d_sq) == 0) return res;
  double d = sqrt(d_sq);
  Pt v = (c2.o - c1.o) / d;
  double c = (c1.r - sign1 * c2.r) / d;
  if (c * c > 1) return res;
  double h = sqrt(max((double)0.0, 1.0 - c * c));
  for (int sign2 = 1; sign2 >= -1; sign2 -= 2) {
    Pt n = Pt(v.x * c - sign2 * h * v.y, v.y * c + sign2 * h * v.x);
    Pt p1 = c1.o + n * c1.r;
    Pt p2 = c2.o + n * (c2.r * sign1);
    if (sign(p1.x - p2.x) == 0 && sign(p1.y - p2.y) == 0)
      p2 = p1 + perp(c2.o - c1.o);
    res.pb({p1, p2});
  }
  return res;
} // 956705

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        Cir c1, c2;
        cin >> c1.o.x >> c1.o.y >> c1.r;
        cin >> c2.o.x >> c2.o.y >> c2.r;
        auto res1 = circles_tangent(c1, c2, 1);
        auto res2 = circles_tangent(c1, c2, -1);
        res1.insert(res1.end(), all(res2));
        double ans = 0;
        for (auto [p, q] : res1) {
            Pt tmp = perp(p - q);
            double c = -(tmp * p);
            double a = tmp.x, b = tmp.y;
            double m = max({fabs(a), fabs(b), fabs(c)});
            ans += fabs(a / m + b / m + c / m);
        }
        cout << fixed << setprecision(10) << ans << "\n";
    }
}
0