No.3344 Common Tangent Line
タグ : / 解いたユーザー数 16
作問者 :
2251799813685248
/ テスター :
noya2
問題文
直交する $2$ つの軸($x$ 軸, $y$ 軸)からなる $xy$ 平面上に $2$ つの円 $1,2$ があります。この $2$ つの円は交点を持たず、どちらかがもう一方の内部に存在することもありません。
円 $1$ は、中心が $(C_{1x},C_{1y})$ 、半径が $r_1$ であり、円 $2$ は、中心が $(C_{2x},C_{2y})$ 、半径が $r_2$ です。
この $2$ つの円の両方に同時に接するような直線 $4$ 本をすべて求め、これらに特定の処理を施すことで $1$ つの実数を求め、その実数を出力してください。
特定の処理については、下部の出力形式を参照してください。
なお、制約の下ではこのような直線は必ずちょうど $4$ つ存在することが示せます。(サンプル1 の画像を参照)
$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- $1 \leq T \leq 2\times 10^{5}$
- $-100 \leq C_{1x},C_{1y},C_{2x},C_{2y} \leq 100$
- $(C_{1x},C_{1y}) \neq (C_{2x},C_{2y})$
- $0 < r_1 \leq r_2 \leq 100$
- $\sqrt{(C_{2x}-C_{1x})^2+(C_{2y}-C_{1y})^2} > r_1+r_2$
- 入力はすべて整数
入力
$T$
$\text{case}_1$
$\text{case}_2$
$\text{case}_3$
$\vdots$
$\text{case}_T$
ただし、各テストケースは以下の形式で与えられます。
$C_{1x} \ \ C_{1y} \ \ r_1$
$C_{2x} \ \ C_{2y} \ \ r_2$
出力
$T$ ケース分出力してください。
各ケースにおいては、まず、 $4$ 本の直線を計 $12$ 個の実数 $a_1,a_2,a_3,a_4,b_1,b_2,b_3,b_4,c_1,c_2,c_3,c_4$ を用いてそれぞれ以下の形式で表してください。
- $a_1x+b_1y+c_1=0$
- $a_2x+b_2y+c_2=0$
- $a_3x+b_3y+c_3=0$
- $a_4x+b_4y+c_4=0$
そして、それぞれの式に対して以下の操作を行ってください。
直線の式を $ax+by+c=0$ とするとき、$M=\text{max}(|a|,|b|,|c|)$ と定める。そして、直線の式の係数全てを $M$ で割る。すなわち、 $a,b,c$ をそれぞれ $\frac{a}{M}, \frac{b}{M}, \frac{c}{M}$ で置き換える。
この操作を $4$ 本の直線それぞれに対して行った結果が以下のようになったとします。(操作後の式の係数を表す文字には'を付けています。)
- $a'_1x+b'_1y+c'_1=0$
- $a'_2x+b'_2y+c'_2=0$
- $a'_3x+b'_3y+c'_3=0$
- $a'_4x+b'_4y+c'_4=0$
最後に、次の式で定められる値 $X$ を求め、出力してください。
$X=|a'_1+b'_1+c'_1| + |a'_2+b'_2+c'_2| + |a'_3+b'_3+c'_3| + |a'_4+b'_4+c'_4|$
この値は、直線の表示方法や直線の順番によらず常に一定であることが示せます。
出力形式
ケース $i$ に対する $X$ の値を $X_i$ と表示する。 $X_1$, $X_2$, $X_3$ $\dots$ $X_T$ を改行区切りで合計 $T$ 行出力してください。
$X_1$ $X_2$ $X_3$ $\vdots$ $X_T$なお、出力は、想定解との絶対誤差が $10^{-4}$ 以下であるときに正解とみなされます。なお、想定解と真の値の絶対誤差は $10^{-9}$ 以下であることが保証されています。
サンプル
サンプル1
入力
3 1 1 1 4 -2 2 16 -34 14 -76 99 29 0 -16 8 0 16 8
出力
3.0923292192132454 4.8406596632442525 4.0000000000000000
サンプル1 の最初のケースについて説明します。
答えのもととなる直線は $4$ 本は、それぞれ以下の式で表されます。(係数を明示しています)
これを特定の操作に従って変換することで出力例の値になります。
- $1x+0y-2=0$
- $0x+1y+0=0$
- $(\text{cos}T) x + (\text{sin}T) y -1 - \text{cos}T - \text{sin}T = 0 \space(T = \frac{\pi}{4} + \text{arcsin}{\frac{1}{3\sqrt{2}}})$
- $(\text{cos}U) x + (\text{sin}U) y -1 - \text{cos}U - \text{sin}U = 0 \space(U = \frac{5}{4} \pi - \text{arcsin}{\frac{1}{3\sqrt{2}}})$
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。