AtCoder ABC183 B「Billiards」の問題文では、開始点Sから進み、x軸でちょうど1回反射した後にゴールGを通るための、x軸上の反射位置のx座標を求めます。
答えは、ゴールG=(Gx,Gy)をx軸について反転したG′=(Gx,-Gy)へ移し、S=(Sx,Sy)からG′を結ぶ直線がy=0を横切る位置です。ABC183 Bの公式解説が使う反射変換を交点までたどると、求める値は(Sx*Gy + Gx*Sy) / (Sy + Gy)になります。
反射を対称な点への直線に置き換える
反射後の線分をx軸について鏡映すると、ゴールGはG′=(Gx,-Gy)に移ります。入射角と反射角が等しいため、開始点Sから反射点を通ってG′へ向かう2本の線分は同一直線上に並びます。したがって、反射点はSとG′を結ぶ線分がx軸と交わる点です。
交点の式をy成分から導く
SからG′へ進む位置を、0≤t≤1の媒介変数でP(t)=S+t(G′-S)と表します。y成分はSy+t(-Gy-Sy)です。これを0と置くと、t=Sy/(Sy+Gy)が得られます。
公式問題文の制約ではSyとGyはどちらも0より大きいため、分母のSy+Gyは必ず正です。y座標はSyから-Gyへ直線的に変化するので、0<t<1となり、線分の途中でy=0を一度だけ通ります。
同じ位置tのx成分はx=Sx+t(Gx-Sx)です。ここへy成分から求めたtを代入すると、
x = Sx + (Sy/(Sy+Gy))(Gx-Sx)
x = (Sx(Sy+Gy)+Sy(Gx-Sx))/(Sy+Gy)
となります。分子を展開するとSx*Syと-Sy*Sxが相殺し、最終的にx=(Sx*Gy+Gx*Sy)/(Sy+Gy)です。分子のSx*Gyは開始点のx座標にゴールの高さを掛けた項、Gx*Syはゴールのx座標に開始点の高さを掛けた項です。
入力から出力までのPythonコード
入力はSx Sy Gx Gyの順に並ぶ4個の整数です。公式問題文ではSxとGxが-106から106まで、SyとGyが0より大きく106以下で、SxとGxは異なります。コードでは入力順に4つの値を読み、導いた式をそのまま計算してxだけを出力します。
sx, sy, gx, gy = map(int, input().split())
x = (sx * gy + gx * sy) / (sy + gy)
print(x)公式サンプルで式を追う
以下の入力と期待出力は公式問題文のサンプルです。入力例1ではS=(1,1)、G=(7,2)なので、反転後の点はG′=(7,-2)です。線分はP(t)=(1+6t, 1-3t)となり、y成分を0にすると1-3t=0からt=1/3です。同じ値をx成分へ入れるとx=1+6*(1/3)=3になります。
公式問題文の入力例1：
1 1 7 2公式問題文の出力例1（期待出力）：
3.0000000000次の2組も公式問題文に掲載された入力と期待出力です。公式出力の小数桁数と、Pythonのprint(x)が表示する桁数は一致しないことがあります。判定では文字列ではなく、公式の誤差条件を使います。
公式問題文の入力例2
1 1 3 2公式問題文の出力例2（期待出力）：
1.6666666667公式問題文の入力例3
-9 99 -999 9999公式問題文の出力例3（期待出力）：
-18.7058823529中点になる独自例
次の例は公式サンプルではありません。Sy=Gy=1ならt=1/2となり、反射位置のx座標はSxとGxの中点です。
独自例の入力：
0 1 2 1この入力ではx=(0*1+2*1)/(1+1)=1となり、掲載コードの出力は次の通りです。
1.0正しさと計算量
Gをx軸対称に移すと、反射する経路はSからG′へ向かう直線になります。その線分のy成分は正のSyから負の-Gyへ一定の割合で変わり、Sy+Gy>0なのでy=0となるtは一つだけです。そのtをx成分へ代入した値が線分とx軸の交点であり、元の反射経路で通る位置に対応します。
公式問題文の許容誤差は、想定値との差の絶対誤差または相対誤差が10-6以下であることです。Python 3の/は整数同士でも浮動小数値を返すため、固定桁数を指定せずprint(x)で出力できます。
処理は4個の入力値を読み、定数回の演算を行うだけなので、時間計算量はO(1)、追加メモリもO(1)です。
