結果
| 問題 |
No.3344 Common Tangent Line
|
| コンテスト | |
| ユーザー |
 ponjuice
|
| 提出日時 | 2025-11-14 11:26:00 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 961 ms / 3,000 ms |
| コード長 | 10,527 bytes |
| コンパイル時間 | 3,646 ms |
| コンパイル使用メモリ | 299,536 KB |
| 実行使用メモリ | 7,716 KB |
| 最終ジャッジ日時 | 2025-11-14 11:26:42 |
| 合計ジャッジ時間 | 36,999 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 40 |
ソースコード
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(ll i = 0; i < n; i++)
#define all(a) a.begin(),a.end()
using Real = long double;
using Point = complex<Real>;
const Real EPS = 1e-8, PI = acos(-1);
istream &operator>>(istream &is, Point& p) {
Real a, b;
is >> a >> b;
p = Point(a, b);
return is;
}
ostream &operator<<(ostream &os, Point p) {
return os << fixed << p.real() << " " << p.imag();
}
Point operator*(Point p, Real d) {
return Point(real(p) * d, imag(p) * d);
}
Point operator/(Point p, Real d) {
return Point(real(p) / d, imag(p) / d);
}
inline bool equal(Real a, Real b){
return fabs(a - b) < EPS;
}
Point unit(Point a) {
return a / abs(a);
}
Point normal(Point a) {
return a * Point(0, 1);
}
Point normalUnit(Point a) {
return unit(normal(a));
}
Real dot(Point a, Point b){
return a.real() * b.real() + a.imag() * b.imag();
}
Real cross(Point a, Point b){
return (a.real() * b.imag() - a.imag() * b.real());
}
Point rotate(Point a, double theta){
return Point(cos(theta) * a.real() - sin(theta) * a.imag(),
sin(theta) * a.real() + cos(theta) * a.imag());
}
Real radianToDegree(Real r) {
return r * 180 / PI;
}
Real degreeToRadian(Real d) {
return d * PI / 180;
}
Real getAngle(Point a, Point b, Point c){
const Point ab(b - a), bc(c - b);
Real s = atan2(ab.imag(), ab.real()), t = atan2(bc.imag(), bc.real());
if(s > t) swap(s,t);
Real theta = t - s;
return min(theta, 2 * PI - theta);
}
struct Line{
Point a,b;
Line() = default;
Line(Point A, Point B) : a(A), b(B) {}
// ax + by = c
Line(Real A, Real B, Real C){
if(equal(A, 0)) a = Point(0, C / B), b = Point(1, C / B);
else if(equal(B, 0)) b = Point(C / A, 0), b = Point(C / A, 1);
else a = Point(0, C / B), b = Point(C / A, 0);
}
friend ostream &operator<<(ostream &os, Line &p) {
return os << p.a << " to " << p.b;
}
friend istream &operator>>(istream &is, Line &a) {
return is >> a.a >> a.b;
}
};
using Segment = Line;
// 点pから線lに垂線を下ろした時の交点
Point projection(Line l, 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;
}
int ccw(Point a, Point b, Point c){
b -= a;
c -= a;
// 反時計回り
if(cross(b, c) > EPS) return 1;
// 時計回り
if(cross(b, c) < -EPS) return -1;
// c-a-bの順番で点がある
if(dot(b, c) < 0) return -2;
// a-b-cの順番で点がある
if(norm(b) < norm(c)) return 2;
// a-b の間にcがある
return 0;
}
bool isParallel(Line a, Line b){
return equal(cross(a.b - a.a, b.b - b.a), 0);
}
bool isOrthogonal(Line a, Line b){
return equal(dot(a.b - a.a, b.b - b.a), 0);
}
bool isIntersect(Segment s, Segment t){
return ccw(s.a, s.b, t.a) * ccw(s.a, s.b, t.b) <= 0 && ccw(t.a, t.b, s.a) * ccw(t.a, t.b, s.b) <= 0;
}
Point crossPoint(Line s, Line t){
Real d1 = cross(s.b - s.a, t.b - t.a);
Real d2 = cross(s.b - s.a, s.b - t.a);
if(equal(d1, 0) && equal(d2, 0)){
if( ccw(t.a, t.b, s.a) == 0) return s.a;
if( ccw(t.a, t.b, s.b) == 0) return s.b;
if( ccw(s.a, s.b, t.a) == 0) return t.a;
if( ccw(s.a, s.b, t.b) == 0) return t.b;
}
return t.a + (t.b - t.a) * (d2 / d1);
}
Real distance(Segment l, Point p){
if(dot(l.b - l.a, p - l.a) < EPS) return abs(p - l.a);
if(dot(l.a - l.b, p - l.b) < EPS) return abs(p - l.b);
return abs(cross(l.b - l.a, p - l.a)) / abs(l.b - l.a);
}
Real ldistance(Line l, Point p){
return abs(cross(l.b - l.a, p - l.a)) / abs(l.b - l.a);
}
Real distance(Segment s, Segment t){
if(isIntersect(s,t)) return 0;
Real res = distance(s,t.a);
res = min(res, distance(s, t.b));
res = min(res, distance(t, s.a));
res = min(res, distance(t, s.b));
return res;
}
Real area(vector<Point>& p){
Real res = 0;
int n = p.size();
rep(i,n){
res += cross(p[i], p[(i + 1) % n]);
}
return res / 2;
}
bool isConvex(vector<Point>& p){
bool res = true;
int n = p.size();
rep(i,n){
if(cross(p[(i+1)%n]-p[i], p[(i+2)%n] - p[(i+1)%n]) < -EPS){
res = false;
}
}
return res;
}
int isContain(vector<Point>& g, Point& p){
bool in = false;
int n = g.size();
rep(i,n){
Point a = g[i] - p, b = g[(i+1)%n] - p;
if(imag(a) > imag(b)){
swap(a, b);
}
if(imag(a) <= EPS && EPS < imag(b) && cross(a, b) < - EPS){
in = !in;
}
if( equal(cross(a, b), 0) && dot(a, b) <= 0){
return 1;
}
}
return in ? 2 : 0;
}
// 直線を含めない場合は <=-EPS を <EPS に変更する
vector<Point> convexHull(vector<Point>& p){
int n = (int)p.size(), k = 0;
sort(all(p), [](const Point &a, const Point &b) {
return (real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b));
});
vector<Point> ch(2 * n);
for(int i = 0; i < n; ch[k++] = p[i++]) {
while(k >= 2 && cross(ch[k - 1] - ch[k - 2], p[i] - ch[k - 1]) <= -EPS)
--k;
}
for(int i = n - 2, t = k + 1; i >= 0; ch[k++] = p[i--]) {
while(k >= t && cross(ch[k - 1] - ch[k - 2], p[i] - ch[k - 1]) <= -EPS)
--k;
}
ch.resize(k - 1);
return ch;
}
Real convexDiameter(vector<Point>& p){
int n = (int)p.size();
int is = 0, js = 0;
for(int i = 1; i < n; i++){
if(imag(p[i]) > imag(p[is])) is = i;
if(imag(p[i]) < imag(p[js])) js = i;
}
Real mx = abs(p[js] - p[is]);
int i = is, j = js;
do {
if(cross(p[(i + 1) % n] - p[i], p[(j + 1) % n] - p[j]) >= 0){
j = (j + 1) % n;
}else{
i = (i + 1) % n;
}
if(abs(p[i] - p[j]) > mx){
mx = abs(p[i] - p[j]);
}
}while(i != is || j != js);
return mx;
}
vector<Point> convexCut(vector<Point>& p, Line l){
vector<Point> res;
int n = (int)p.size();
for(int i = 0; i < n; i++){
if(ccw(l.a, l.b, p[i]) != -1) res.emplace_back(p[i]);
if(ccw(l.a, l.b, p[i]) * ccw(l.a, l.b, p[(i + 1) % n]) < 0){
res.emplace_back(crossPoint(Line(p[i], p[(i + 1) % n]), l));
}
}
return res;
}
struct Circle{
Point p;
Real r;
Circle() = default;
Circle(Point p, Real r) : p(p), r(r) {}
};
int isIntersect(Circle a, Circle b){
double d = abs(a.p - b.p);
// 2つの円が離れている場合
if(d > a.r + b.r + EPS) {
return 4;
}
// 外接している場合
if(equal(d, a.r + b.r)) {
return 3;
}
// 内接している場合
if(equal(d, abs(a.r - b.r))) {
return 1;
}
// 内包している場合
if(d < abs(a.r - b.r) - EPS) {
return 0;
}
return 2;
}
Circle inCircle(Point a, Point b, Point c){
Real A = abs(b - c), B = abs(a - c), C = abs(a - b);
Point p(A * real(a) + B * real(b) + C * real(c),
A * imag(a) + B * imag(b) + C * imag(c));
p /= (A + B + C);
Real r = distance(Line(a, b), p);
return Circle(p, r);
}
Circle outCircle(Point a, Point b, Point c){
Point f = (a + b) / 2, s = (b + c) / 2;
Line A(f, normal(b - f) + f), B(s, normal(c - s) + s);
Point m = crossPoint(A,B);
Real r = abs(a - m);
r = max(r, abs(b - m));
r = max(r, abs(c - m));
return Circle(m, r);
}
vector<Point> crossPoint(Circle c, Line l) {
vector<Point> res;
Real d = ldistance(l, c.p);
// 交点を持たない
if(d > c.r + EPS) {
return res;
}
// 接する
Point h = projection(l, c.p);
if(equal(d, c.r)) {
res.emplace_back(h);
return res;
}
Point e = unit(l.b - l.a);
Real ph = sqrt(c.r * c.r - d * d);
res.emplace_back(h - e * ph);
res.emplace_back(h + e * ph);
return res;
}
vector<Point> crossPoint(Circle c1, Circle c2) {
vector<Point> res;
int mode = isIntersect(c1, c2);
Real d = abs(c1.p - c2.p);
if(mode == 4) {
return res;
}
if(mode == 0) {
return res;
}
if(mode == 3) {
Real t = c1.r / (c1.r + c2.r);
res.emplace_back(c1.p + (c2.p - c1.p) * t);
return res;
}
if(mode == 1) {
if(c2.r < c1.r - EPS) {
res.emplace_back(c1.p + (c2.p - c1.p) * (c1.r / d));
} else {
res.emplace_back(c2.p + (c1.p - c2.p) * (c2.r / d));
}
return res;
}
Real rc1 = (c1.r * c1.r + d * d - c2.r * c2.r) / (2 * d);
Real rs1 = sqrt(c1.r * c1.r - rc1 * rc1);
if(c1.r - abs(rc1) < EPS) {
rs1 = 0;
}
Point e12 = (c2.p - c1.p) / abs(c2.p - c1.p);
res.emplace_back(c1.p + rc1 * e12 + rs1 * e12 * Point(0, 1));
res.emplace_back(c1.p + rc1 * e12 + rs1 * e12 * Point(0, -1));
return res;
}
vector<Point> tangentToCircle(Point p, Circle c) {
return crossPoint(c, Circle(p, sqrt(norm(c.p - p) - c.r * c.r)));
}
vector<Line> tangent(Circle a, Circle b) {
vector<Line> ret;
// 2円の中心間の距離
Real g = abs(a.p - b.p);
// 円が内包されている場合
if(equal(g, 0)) {
return ret;
}
Point u = unit(b.p - a.p);
Point v = rotate(u, PI / 2);
for(int s : {-1, 1}) {
double h = (a.r + b.r * s) / g;
if(equal(h * h, 1)) {
ret.emplace_back(a.p + (h > 0 ? u : -u) * a.r,
a.p + (h > 0 ? u : -u) * a.r + v);
} else if(1 - h * h > 0) {
Point U = u * h, V = v * sqrt(1 - h * h);
ret.emplace_back(a.p + (U + V) * a.r, b.p - (U + V) * (b.r * s));
ret.emplace_back(a.p + (U - V) * a.r, b.p - (U - V) * (b.r * s));
}
}
return ret;
}
void solve() {
Point p1, p2;
Real r1, r2;
cin >> p1 >> r1 >> p2 >> r2;
Circle c1(p1, r1), c2(p2, r2);
vector<Line> ret = tangent(c1, c2);
Real ans = 0;
rep(i,ret.size()) {
Real a, b, c;
// ax + by + c = 0 という形にする
a = ret[i].b.imag() - ret[i].a.imag();
b = ret[i].a.real() - ret[i].b.real();
c = - (a * ret[i].a.real() + b * ret[i].a.imag());
Real mx = max({abs(a), abs(b), abs(c)});
a /= mx; b /= mx; c /= mx;
ans += abs(a + b + c);
}
cout << ans << endl;
}
int main() {
cout << fixed << setprecision(20);
int t;
cin >> t;
while(t--) solve();
}