ZONe2021 B問題友好の印数学問題の解説 - 競技プログラミング悪戦苦闘日記

ZONe2021 B問題の解説です。
中学の数学の座標の扱いを覚えていれば解ける問題です。

問題

あなたは今、高さ 1000 の非常に高いタワーの下にいます。タワーから距離 D 離れた位置の上空 H の高さに UFO がおり（入出力例 1 の図を参照してください）、あなたは UFO に電波を届けたいです。
タワーと UFO の間には遮蔽物が N 個あります。i 番目の遮蔽物はタワーから UFO の方向に向かって距離 $d_i$ の場所に位置していて、高さは $h_i$ です。
あなたはタワーを上って、あなたと UFO の間の直線上に遮蔽物が 1 つも無い状態にしたいです。上る必要のある最低の高さを求めてください。
なお、地面は凹凸のない水平面であり、タワー及び遮蔽物は地面と垂直に建っているものとします。
また、あなたと UFO の間の直線上にちょうど遮蔽物の上端があるとき、その遮蔽物には遮蔽されていないものとします。

解き方の方針

それぞれの遮蔽物の頂点座標とUFOの位置を直線で結んで、y切片（ $x = 0$ の時のyの位置）を求めます。y切片の最大値が答えです。

f:id:hrksb5029:20210502215810p:plain — 解き方のイメージ

UFOのx, y座標が $(D, H)$ 、遮蔽物のx, y座標が $(d, h)$ のとき、 $x=0$ の時のyは以下のように求められます。
まず傾きはyの増分をxの増分で割って $(H - h) / (D - d)$ になり、次の式が得られます。
$y = \frac{(H - h)}{(D - d)}x - b$
ここで $b$ を求めるにはxとyにそれぞれUFOの座標か遮蔽物の座標を代入します。
UFOの座標を代入すると以下のようになります。
$H = \frac{(H - h)}{(D - d)}D - b \\ \Leftrightarrow b = \frac{(H - h)}{(D - d)}D - H$

実装

単純に遮蔽物ごとにx=0の時のyの値を求めて、その最大値を答えとします。

N, D, H = map(int, input().split())
ans = 0
for i in range(N):
    d, h = map(int, input().split())
    b = (D*h - d*H) / (D - d)
    ans = max(ans, b)
print(ans)