結果
| 問題 |
No.3344 Common Tangent Line
|
| コンテスト | |
| ユーザー |
 tassei903
|
| 提出日時 | 2025-10-31 12:17:24 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 16,786 bytes |
| コンパイル時間 | 283 ms |
| コンパイル使用メモリ | 82,432 KB |
| 実行使用メモリ | 123,216 KB |
| 最終ジャッジ日時 | 2025-11-13 21:09:58 |
| 合計ジャッジ時間 | 9,477 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | -- * 1 |
| other | TLE * 1 -- * 39 |
ソースコード
import sys
input = lambda :sys.stdin.readline()[:-1]
ni = lambda :int(input())
na = lambda :list(map(int,input().split()))
yes = lambda :print("yes");Yes = lambda :print("Yes");YES = lambda : print("YES")
no = lambda :print("no");No = lambda :print("No");NO = lambda : print("NO")
#######################################################################
import math
from fractions import Fraction
class QuadraticNumber:
"""
p + q * sqrt(r) の形の数を表すクラス。
p, q は有理数 (Fraction)、r は 0 以上の整数(int)を想定しています。
"""
def __init__(self, p, q, r):
# p, q を Fraction (有理数) に変換
self.p = Fraction(p)
self.q = Fraction(q)
if not isinstance(r, int):
raise TypeError("r は整数である必要があります。")
if r < 0:
raise ValueError("r は 0 以上の整数である必要があります。")
# r を正規化（平方因子を q に移動）
q_factor, simplified_r = self._simplify_sqrt(r)
self.q *= q_factor
self.r = simplified_r
# r=1 (sqrt(1)=1) の場合、q を p に吸収
if self.r == 1:
self.p += self.q
self.q = Fraction(0)
self.r = 0 # r=0 (sqrt(0)=0) と同じ扱いに
# q=0 なら r は何でもよいが、比較のために 0 に統一
if self.q == 0:
self.r = 0
def _simplify_sqrt(self, r_val):
"""[ヘルパー] sqrt(r_val) を factor * sqrt(simplified_r) に変換する"""
if r_val <= 0:
return 1, r_val
if r_val == 1:
return 1, 1 # sqrt(1) = 1 * sqrt(1)
factor = 1
i = 2
temp_r = r_val
# r_val から平方因子 i*i を見つけて外に出す
while i * i <= temp_r:
if temp_r % (i * i) == 0:
temp_r //= (i * i)
factor *= i
else:
i += 1
# 例: r_val=8 -> factor=2, temp_r=2 (2*sqrt(2))
# 例: r_val=12 -> factor=2, temp_r=3 (2*sqrt(3))
return factor, temp_r
# --- 表現 ---
def __repr__(self):
"""デバッグ用の公式表現"""
return f"QuadraticNumber(p={self.p}, q={self.q}, r={self.r})"
def __str__(self):
"""人間が読みやすい文字列表現"""
# q*sqrt(r) の部分を構築
sqrt_part = ""
if self.q == 0 or self.r == 0:
sqrt_part = ""
else:
# q の符号と値に応じて整形
q_str = ""
if self.q == 1:
q_str = " + "
elif self.q == -1:
q_str = " - "
elif self.q > 0:
q_str = f" + {self.q}"
else: # q < 0
q_str = f" - {-self.q}"
# q が分数の場合 (e.g., 1/2) は * を明記
if self.q.denominator != 1 and self.q not in [1, -1]:
q_str += "*"
sqrt_part = f"{q_str}sqrt({self.r})"
# p の部分と結合
if self.p == 0:
if not sqrt_part:
return "0"
# " + 2*sqrt(3)" -> "2*sqrt(3)"
return sqrt_part.lstrip(" +")
else:
if not sqrt_part:
return str(self.p)
# p があり、sqrt_part が " + ..." または " - ..." の場合
return f"{self.p}{sqrt_part}"
# --- 演算のためのヘルパー ---
def _check_other(self, other):
"""演算相手を QuadraticNumber に変換し、r が一致するか確認"""
if isinstance(other, (int, float)) or isinstance(other, Fraction):
# 相手が通常の数値なら、q=0, r=0 として扱う
# (self.r が 0 でない場合、演算メソッド側で r を適切に処理する)
other = QuadraticNumber(other, 0, 0)
if not isinstance(other, QuadraticNumber):
return NotImplemented
return other
def _determine_r(self, other):
"""[ヘルパー] 演算後の r を決定する (片方が 0 の場合を考慮)"""
if self.r != 0:
return self.r
if other.r != 0:
return other.r
return 0 # 両方 0
# --- 四則演算 ---
def __add__(self, other):
other = self._check_other(other)
if other is NotImplemented:
return NotImplemented
# r が異なり、どちらも 0 でない場合はエラー
if self.r != other.r and (self.r != 0 and other.r != 0):
raise TypeError(f"sqrt({self.r}) と sqrt({other.r}) の加減算はサポートされていません。")
new_r = self._determine_r(other)
new_p = self.p + other.p
# (p1 + q1*sqrt(r1)) + (p2 + q2*sqrt(r2))
new_q = Fraction(0)
if self.r == other.r:
new_q = self.q + other.q
elif self.r != 0: # other.r == 0
new_q = self.q
elif other.r != 0: # self.r == 0
new_q = other.q
return QuadraticNumber(new_p, new_q, new_r)
def __radd__(self, other):
return self.__add__(other) # (other + self)
def __sub__(self, other):
other = self._check_other(other)
if other is NotImplemented:
return NotImplemented
if self.r != other.r and (self.r != 0 and other.r != 0):
raise TypeError(f"sqrt({self.r}) と sqrt({other.r}) の加減算はサポートされていません。")
new_r = self._determine_r(other)
new_p = self.p - other.p
new_q = Fraction(0)
if self.r == other.r:
new_q = self.q - other.q
elif self.r != 0: # other.r == 0
new_q = self.q
elif other.r != 0: # self.r == 0
new_q = -other.q # (self.p - (p2 + q2*sqrt(r2)))
return QuadraticNumber(new_p, new_q, new_r)
def __rsub__(self, other):
# other - self
other = self._check_other(other)
if other is NotImplemented:
return NotImplemented
return other.__sub__(self)
def __mul__(self, other):
other = self._check_other(other)
if other is NotImplemented:
return NotImplemented
if self.r != other.r and (self.r != 0 and other.r != 0):
raise TypeError(f"sqrt({self.r}) と sqrt({other.r}) の乗算はサポートされていません。")
# (p1 + q1*sqrt(r1)) * (p2 + q2*sqrt(r2))
# r1=0 の場合: p1 * (p2 + q2*sqrt(r2)) = p1*p2 + p1*q2*sqrt(r2)
if self.r == 0:
return QuadraticNumber(self.p * other.p, self.p * other.q, other.r)
# r2=0 の場合: (p1 + q1*sqrt(r1)) * p2 = p1*p2 + q1*p2*sqrt(r1)
if other.r == 0:
return QuadraticNumber(self.p * other.p, self.q * other.p, self.r)
# r1 == r2 == r の場合
# (p1*p2 + q1*q2*r) + (p1*q2 + q1*p2)*sqrt(r)
new_p = self.p * other.p + self.q * other.q * self.r
new_q = self.p * other.q + self.q * other.p
return QuadraticNumber(new_p, new_q, self.r)
def __rmul__(self, other):
return self.__mul__(other) # (other * self)
def __truediv__(self, other):
other = self._check_other(other)
if other is NotImplemented:
return NotImplemented
# (p1 + q1*sqrt(r1)) / (p2 + q2*sqrt(r2))
# Case 1: self / (p2 + 0) (r2=0)
if other.r == 0:
if other.p == 0:
raise ZeroDivisionError("0 で除算しました。")
return QuadraticNumber(self.p / other.p, self.q / other.p, self.r)
# Case 2: (p1 + 0) / (p2 + q2*sqrt(r2)) (r1=0)
# 分母の有理化: p1 * (p2 - q2*sqrt(r2)) / (p2^2 - q2^2*r2)
if self.r == 0:
denom = other.p**2 - other.q**2 * other.r
if denom == 0:
raise ZeroDivisionError(f"{other} で割ろうとしましたが、(p^2 - q^2*r) が 0 になりました。")
num_p = self.p * other.p
num_q = -self.p * other.q
return QuadraticNumber(num_p / denom, num_q / denom, other.r)
# Case 3: r1 != r2 (and both != 0)
if self.r != other.r:
raise TypeError(f"sqrt({self.r}) と sqrt({other.r}) の除算はサポートされていません。")
# Case 4: r1 == r2 == r (and r != 0)
# 分母: p2^2 - q2^2*r
denom = other.p**2 - other.q**2 * self.r
if denom == 0:
raise ZeroDivisionError(f"{other} で割ろうとしましたが、(p^2 - q^2*r) が 0 になりました。")
# 分子: (p1 + q1*sqrt(r)) * (p2 - q2*sqrt(r))
# = (p1*p2 - q1*q2*r) + (q1*p2 - p1*q2)*sqrt(r)
num_p = self.p * other.p - self.q * other.q * self.r
num_q = self.q * other.p - self.p * other.q
return QuadraticNumber(num_p / denom, num_q / denom, self.r)
def __rtruediv__(self, other):
# other / self
# other は int/float/Fraction のはず
other_q = QuadraticNumber(other, 0, 0)
return other_q.__truediv__(self)
# --- べき乗 ---
def __pow__(self, n):
if not isinstance(n, int):
raise TypeError("べき指数 n は整数である必要があります。")
if n == 0:
return QuadraticNumber(1, 0, 0) # x^0 = 1
if n < 0:
# x^(-n) = 1 / (x^n)
one = QuadraticNumber(1, 0, 0)
base_pow = self**(-n)
return one / base_pow
# 繰り返し二乗法 (n > 0)
result = QuadraticNumber(1, 0, self.r)
temp = self
while n > 0:
if n % 2 == 1:
result = result * temp
temp = temp * temp
n //= 2
return result
# --- 比較演算 ---
def __eq__(self, other):
try:
other = self._check_other(other)
except TypeError:
# r が異なる (e.g. sqrt(2) vs sqrt(3)) 場合は False
return False
if other is NotImplemented:
return False
# (p1 + q1*sqrt(r1)) == (p2 + q2*sqrt(r2))
# r1=0, r2=0 (両方とも有理数)
if self.r == 0 and other.r == 0:
return self.p == other.p
# r1=0, r2!=0: (p1 + 0) == (p2 + q2*sqrt(r2))
# -> p1==p2 かつ q2==0 が必要
if self.r == 0:
return self.p == other.p and other.q == 0
# r1!=0, r2=0: (p1 + q1*sqrt(r1)) == (p2 + 0)
# -> p1==p2 かつ q1==0 が必要
if other.r == 0:
return self.p == other.p and self.q == 0
# r1 == r2 != 0
if self.r == other.r:
# r が正規化されているので、p, q, r が一致すれば等しい
return self.p == other.p and self.q == other.q
# r1 != r2 (and both != 0)
# r が正規化されているので、基底が異なれば等しくない
return False
def __ne__(self, other):
return not self.__eq__(other)
def to_float(self):
"""浮動小数点数（float）に変換"""
if self.r == 0:
return float(self.p)
return float(self.p + self.q * math.sqrt(self.r))
# --- 大小比較 (浮動小数点数で行う) ---
def __lt__(self, other):
if isinstance(other, (int, float, Fraction)):
return self.to_float() < float(other)
if isinstance(other, QuadraticNumber):
return self.to_float() < other.to_float()
return NotImplemented
def __le__(self, other):
if isinstance(other, (int, float, Fraction)):
return self.to_float() <= float(other)
if isinstance(other, QuadraticNumber):
return self.to_float() <= other.to_float()
return NotImplemented
def __gt__(self, other):
if isinstance(other, (int, float, Fraction)):
return self.to_float() > float(other)
if isinstance(other, QuadraticNumber):
return self.to_float() > other.to_float()
return NotImplemented
def __ge__(self, other):
if isinstance(other, (int, float, Fraction)):
return self.to_float() >= float(other)
if isinstance(other, QuadraticNumber):
return self.to_float() >= other.to_float()
return NotImplemented
def _is_non_negative(self):
"""[ヘルパー] self >= 0 かどうかを厳密に判定する (p, q は Fraction)"""
# self.q == 0 (有理数) の場合
if self.q == 0:
return self.p >= 0
# --- self.q != 0 の場合 ---
# __init__ で r=0, r=1 は q=0 に正規化されるため、
# ここに来る時点で self.r > 1 と仮定できる
if self.q > 0:
if self.p >= 0:
# (正 or 0) + (正)
return True
else:
# p < 0, q > 0
# p + q*sqrt(r) >= 0 <=> q*sqrt(r) >= -p
# 両辺 (> 0) を2乗 (p**2 は (-p)**2 と同じ)
return self.q**2 * self.r >= self.p**2
else: # self.q < 0
if self.p <= 0:
# (負 or 0) + (負)
return False
else:
# p > 0, q < 0
# p + q*sqrt(r) >= 0 <=> p >= -q*sqrt(r)
# 両辺 (> 0) を2乗 (q**2 は (-q)**2 と同じ)
return self.p**2 >= self.q**2 * self.r
# --- 演算 (abs) ---
def __abs__(self):
"""
数の絶対値 (mathematical absolute value) を返す。
self >= 0 なら self を、 self < 0 なら -self を返す。
"""
if self._is_non_negative():
# self (>= 0)
return QuadraticNumber(self.p, self.q, self.r)
else:
# -self
return QuadraticNumber(-self.p, -self.q, self.r)
def __float__(self):
"""float(self) の呼び出しに対応 (浮動小数点数に変換)"""
if self.r == 0:
return float(self.p)
# math.sqrt() を使うため、
# ファイルの先頭で import math が必要です
return float(self.p + self.q * math.sqrt(self.r))
for _ in range(ni()):
x1, y1, r1 = map(int, input().split())
x2, y2, r2 = map(int, input().split())
def common_tangent_lines(x1, y1, r1, x2, y2, r2):
result = []
xd = x2 - x1; yd = y2 - y1
rr0 = xd**2 + yd**2
if (r1 - r2)**2 <= rr0:
cv = r1 - r2
if rr0 == (r1 - r2)**2:
assert False
else:
px = QuadraticNumber(cv * xd, -yd, rr0 - cv ** 2)
py = QuadraticNumber(cv * yd, xd, rr0 - cv ** 2)
result.append([
(x1 + r1*px/rr0, y1 + r1*py/rr0),
(x2 + r2*px/rr0, y2 + r2*py/rr0),
])
qx = QuadraticNumber(cv * xd, yd, rr0 - cv ** 2)
qy = QuadraticNumber(cv * yd, -xd, rr0 - cv ** 2)
result.append([
(x1 + r1*qx/rr0, y1 + r1*qy/rr0),
(x2 + r2*qx/rr0, y2 + r2*qy/rr0),
])
if (r1 + r2)**2 <= rr0:
cv = r1 + r2
if rr0 == (r1 + r2)**2:
assert False
else:
px = QuadraticNumber(cv * xd, -yd, rr0 - cv ** 2)
py = QuadraticNumber(cv * yd, xd, rr0 - cv ** 2)
result.append([
(x1 + r1*px/rr0, y1 + r1*py/rr0),
(x2 - r2*px/rr0, y2 - r2*py/rr0),
])
qx = QuadraticNumber(cv * xd, yd, rr0 - cv ** 2)
qy = QuadraticNumber(cv * yd, -xd, rr0 - cv ** 2)
result.append([
(x1 + r1*qx/rr0, y1 + r1*qy/rr0),
(x2 - r2*qx/rr0, y2 - r2*qy/rr0),
])
return result
result = sorted(common_tangent_lines(x1, y1, r1, x2, y2, r2))
ans = 0
for (p1, p2) in result:
# 二点を通る直線の方程式 Ax + By + C = 0 の A, B, C を求める
A = p2[1] - p1[1]
B = p1[0] - p2[0]
C = p2[0] * p1[1] - p1[0] * p2[1]
# print(A, B, C)
z = max(abs(A), abs(B), abs(C))
A /= z
B /= z
C /= z
# print(A, B, C)
ans += float(abs(A + B + C))
print(ans)