結果

問題 No.3344 Common Tangent Line
コンテスト
ユーザー tnakao0123
提出日時 2025-11-15 17:11:07
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 206 ms / 3,000 ms
コード長 3,057 bytes
コンパイル時間 548 ms
コンパイル使用メモリ 62,696 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-11-15 17:11:28
合計ジャッジ時間 19,913 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 40
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:82:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   82 |   scanf("%d", &tn);
      |   ~~~~~^~~~~~~~~~~
main.cpp:86:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   86 |     scanf("%d%d%d%d%d%d", &c0x, &c0y, &r0, &c1x, &c1y, &r1);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

/* -*- coding: utf-8 -*-
 *
 * 3344.cc:  No.3344 Common Tangent Line - yukicoder
 */

#include<cstdio>
#include<cmath>
#include<algorithm>

using namespace std;

/* constant */

/* typedef */

template <typename T>
struct Pt {
  T x, y;
  Pt() {}
  Pt(T _x, T _y) : x(_x), y(_y) {}
  Pt(const Pt<T> &p) : x(p.x), y(p.y) {}

  Pt<T> operator+(const Pt<T> p) const { return Pt<T>(x + p.x, y + p.y); }
  Pt<T> operator-() const { return Pt<T>(-x, -y); }
  Pt<T> operator-(const Pt<T> p) const { return Pt<T>(x - p.x, y - p.y); }
  Pt<T> operator*(T t) const { return Pt<T>(x * t, y * t); }
  Pt<T> operator/(T t) const { return Pt<T>(x / t, y / t); }
  T dot(Pt<T> v) const { return x * v.x + y * v.y; }
  T cross(Pt<T> v) const { return x * v.y - y * v.x; }
  Pt<T> mid(const Pt<T> p) { return Pt<T>((x + p.x) / 2, (y + p.y) / 2); }
  T d2() { return x * x + y * y; }
  double d() { return sqrt(d2()); }

  Pt<T> rot(double th) {
    double c = cos(th), s = sin(th);
    return Pt<T>(c * x - s * y, s * x + c * y);
  }

  Pt<T> rot90() { return Pt<T>(-y, x); }

  bool operator==(const Pt<T> pt) const { return x == pt.x && y == pt.y; }
  bool operator<(const Pt<T> &pt) const {
    return x < pt.x || (x == pt.x && y < pt.y);
  }

  void print() { printf("(%d,%d)", x, y); }
};

using pt = Pt<double>;

struct Line {
  double a, b, c;
  Line() {}
  Line(double _a, double _b, double _c): a(_a), b(_b), c(_c) {}

  double val() {
    double m = max(max(abs(a), abs(b)), abs(c));
    double x = abs(a + b + c) / m;
    return x;
  }
};

/* global variables */

/* subroutines */

Line calcline(pt p, pt v) {
  // (x,y) = p+v*t -> x=px+vx*t, y=py+vy*t
  // -> t=(x-px)/vx=(y-py)/vy
  // -> vy(x-px)=vx(y-py)
  // -> vy*x-vy*px=vx*y-vx*py
  // -> vy*x-vx*y+(vx*py-vy*px)=0
  auto ln = Line(v.y, -v.x, v.x * p.y - v.y * p.x);
  //printf(" %lf*x + %lf*y + %lf = 0\n", ln.a, ln.b, ln.c);
  return ln;
}

/* main */

int main() {
  int tn;
  scanf("%d", &tn);

  while (tn--) {
    int c0x, c0y, r0, c1x, c1y, r1;
    scanf("%d%d%d%d%d%d", &c0x, &c0y, &r0, &c1x, &c1y, &r1);

    pt c0(c0x, c0y), c1(c1x, c1y);
    pt v10 = c0 - c1;
    double l10 = v10.d();
    pt nv10 = v10 / l10;

    pt pa, va, pb, vb;
    if (r0 < r1) {
      // r0:r1=l:l+l10 -> r0(l+l10)=r1*l ->(r1-r0)*l=r0*l10
      // -> l=(r0*l10)/(r1-r0)
      double l = l10 * r0 / (r1 - r0);
      pt c2 = nv10 * l + c0;
      double th = asin(r0 / l);
      pt nva = (-nv10).rot(th), nvb = (-nv10).rot(-th);
      pa = c2, va = nva;
      pb = c2, vb = nvb;
    }
    else {
      pt rva = nv10.rot90(), rvb = -rva;
      pa = rva * r0 + c0, va = nv10;
      pb = rvb * r0 + c0, vb = nv10;
    }

    auto f0 = calcline(pa, va);
    auto f1 = calcline(pb, vb);

    double l12 = l10 * r1 / (r0 + r1), l02 = l10 - l12;
    pt c2 = nv10 * l12 + c1;
    double th = asin(r0 / l02);
    pt nva = nv10.rot(th), nvb = nv10.rot(-th);

    auto f2 = calcline(c2, nva);
    auto f3 = calcline(c2, nvb);

    double v = f0.val() + f1.val() + f2.val() + f3.val();
    printf("%.14lf\n", v);
  }

  return 0;
}
0