B - 友好の印

この問題で必要な予備知識3つ

1. 直線の方程式は y = ax + b で表される。

2. a は変化の割合で、a = (yの増加量) / (xの増加量) と表される。

3. b は切片で、1. の式を変形すると b = y - ax と表される。

・初期値

座標 (0, 0) と座標(D, H) を結ぶ直線を考えると、a = (H - 0) / (D - 0) = H/D , より y = H/D * x となる。

当たり前ですが、遮蔽物が0個のときはそのまま y = 0 の地点にいれば良いので、答えは 0 です。

0 の地点から遮られてしまう場合にはタワーを上りUFOが見える位置に移動しますが、なるべく低い位置を答えとする必要があります。

・各入力に対する処理

パターン1　解を更新しなければいけないとき

上の図では、現時点で持っている解の座標 (0, Y) とUFOの座標 (D, H) を赤線で結んでいます。
そして n 回目の入力で与えられた座標 (d, h) とUFOの座標を緑の線で結んでいます。

この時、赤線を (d, h) が遮っている (= 赤線よりも上に入力された座標がある)ことがわかります。
これを言い換えると、「赤線の変化の割合 > 緑の線の変化の割合」となります。(座標 (D, H) から見ると左下に向かって伸びる線の傾き具合が赤の方が大きいため)

つまり、「(0, Y) (D, H) の傾き > (d, h) (D, H) の傾き」なら解を更新するということです。
それぞれの傾きは  (H - Y) / (D - 0) と (H - h) / (D - d) で表すことができます。

ここまでをコードで書くと以下のようになります。

↓ C++

int N, D, H;
cin >> N >> D >> H;
double Y = 0;
 
for (int i = 0; i < N; i++) {
    int d, h;
    cin >> d >> h;
    if (1.0 * (H - Y) / D > 1.0 * (H - h) / (D - d)) {
        // 解を更新
    }
}

↓ Python

N, D, H = map(int,input().split())
Y = 0

for i in range(N):
  d, h = map(int,input().split())
  if (H - Y) / D > (H - h) / (D - d):
    # 解を更新

パターン2 解を更新しない場合

パターン1の逆バージョンなので、ほとんど省略します。

上の図のように、赤線よりも入力された座標の方が下にある場合は更新しません。
つまり、緑の線の傾きの方が大きければ更新しません。

コード上では更新しない (elseの) 場合の処理を特に書く必要がないので、ここに書くことも特にありません。

ちなみに、赤線上に入力された座標がちょうど乗っかっているような場合にも値の更新をする必要はありません。
「あなたと UFO の間の直線上にちょうど遮蔽物の上端があるとき、その遮蔽物には遮蔽されていないものとします。」と問題文に書いていました。

・値の更新の仕方

この図より、緑の線を伸ばしてY軸とぶつかった時の Y' の点で解を更新すれば良いとわかります。
そしてこれは緑の線の切片とも捉えることができます。

つまりここで、冒頭に書いた予備知識の3番目「 b = y - ax 」を使うことになります。

a の値は、先程 if 文中に書いた 1.0 * (H - h) / (D - d) という値で、x　と y の値は (d, h) か (D, H) の好きなほうを使って代入します。
(ここでは (d, h) を使うことにします。)

すると、 b = y - ax = (h) - (1.0 * (H - h) / (D - d)) * (d) と表すことができ、この値で解を更新します。

↓ C++

if (1.0 * (H - Y) / D > 1.0 * (H - h) / (D - d)) {
    // 解を更新
    Y = h - 1.0 * (H - h) / (D - d) * d;
}

↓ Python

if (H - Y) / D > (H - h) / (D - d):
  # 解を更新
  Y = h - (H - h) / (D - d) * d

ここまでの処理を行ったら、最後に Y の値を出力して終了です。
(傾きの値を前計算するように書き換えています。)

(d, h をdouble型で受け取るとキャストなど考えずにかなり楽にかけますが、入力が全て整数ということを意識しながら今回は一応このような形で書きました)

・完成形

↓ C++ 提出リンク

 #include  <iostream>
using namespace std;

int main() {
  int N, D, H;
  cin >> N >> D >> H;
  double Y = 0;
  double A = 1.0 * H / D;
 
  for (int i = 0; i < N; i++) {
     int d, h;
     cin >> d >> h;
     double a = 1.0 * (H - h) / (D - d);
     if (A > a) {
        // 解を更新
        Y = h - a * d;
        A = a;
     }
  }
  printf("%.10f\n",Y);
}

↓ Python 提出リンク

N, D, H = map(int,input().split())
Y = 0
A = H / D

for i in range(N):
 d, h = map(int,input().split())
 a = (H - h) / (D - d)
 if A > a:
   # 解を更新
   Y = h - a * d
   A = a
print(Y)

※ 割と最後まで書いた後に式を間違えて書いていたことに気づき、一通り修正したつもりですがもし何か矛盾が残っていたら教えて頂けると幸いです。

最後までお読み頂きありがとうございました。