高橋君が訓練を行う回数で二分探索を行います。

答えを \(X\) に決め打ったとします。

はじめに \(N\) 頂点のグラフを用意し、\(XP_i \geq |x_i-x_j| + |y_i-y_j|\) ならば頂点 \(i\) から頂点 \(j\) へ有向辺を貼ります。

最初のジャンプ台をどこにするかは全探索しましょう。始点を決めた際、その始点から全ての頂点に到達できるかは BFS(幅優先探索) により \(\mathrm{O}(N^2)\) で求められます。始点を全探索しているので、結局答えを決め打った時の判定問題は \(\mathrm{O}(N^3)\) で解けます。BFS ではなくワーシャルフロイド法を用いても良いです。

以上より、\(|x_i|,|y_i|\) の最大値を \(\mathrm{MAX}\) として、この問題は \(\mathrm{O}(N^3 \log \mathrm{MAX})\) で解けました。

二分探索の上限には注意してください。今回の問題の場合、最大で答えは \(4\times 10^9\) となり、これは 32 bit 整数型には収まりません。