Sign of Friendship [ZONeエナジー プログラミングコンテスト “HELLO SPACE” B]

https://atcoder.jp/contests/zone2021/tasks/zone2021_b

解説

https://atcoder.jp/contests/zone2021/submissions/22237510

この問題は数学的な知識が要求される。
自分は大学時代に塾講師をしていたので、似たような問題を死ぬほど中学生に教えた経験が競プロで生きた。

どのような方針で行くか

今回は答えが小数であるため、答えを1,2,3,...のように全探索するような形で解くことは難しい。
だが、答えの候補を全探索はできる。
全ての遮蔽物について、遮蔽物とUFOをつないだ直線を書いたときのタワーの交点での高さを考える。
今回の答えはこのいずれかが答えとなる。
例えば、遮蔽物1とUFOとをつないだ直線とタワーとの交点での高さをx1とすると、x1の位置ではその遮蔽物越しにギリギリ見られることになる。
他の全ての遮蔽物がこれよりも低いならば、これ以上高くする必要はないし、他の遮蔽物2が遮っているならば、その遮蔽物で見られる高さx2に移動すればいい。
よって、最終的な見られる高さとして最低のものは、全ての遮蔽物において、遮蔽物とUFOをつないだ直線を書いたときのタワーの交点の最大値となる。
あとは、遮蔽物とUFOをつないだ直線を書いたときのタワーの交点の高さをいかに求めるかである。

TL見てたら、直線で切片見ればいいですね…

確かに…

台形と相似比（自分はこれで解いた…）

中学で習う（少なくとも自分の時は）知識を使って解く。
結論からいうと、距離d, 高さhの遮蔽物と距離D, 高さHのUFOをつないだ時のタワーの交点の高さは

(dH-Dh)/(d-D)

となる。
台形ができるので、適当に対角線を引くと相似比によって2つの三角形で立式でき、式変形するとこれが出てくる。
「相似比 台形」あたりでググると関連情報が得られる。
相似比と線分1
ここで紹介されている解法が近い。

int N, D, H, d[101], h[101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> D >> H;
    rep(i, 0, N) cin >> d[i] >> h[i];

    double ans = 0;
    rep(i, 0, N) chmax(ans, (1.0 * d[i] * H - 1.0 * D * h[i]) / (1.0 * d[i] - 1.0 * D));
    printf("%.10f\n", ans);
}