Do the binary search by how many times Takahashi trains.

Let’s say we suppose the answer is \(X\).

First, prepare a graph of \(N\) vertices. If \(XP_i \geq |x_i-x_j| + |y_i-y_j|\), then add a directed edge from Vertex \(i\) to Vertex \(j\).

Let us brute force the initial trampoline. Once we fixed the initial trampoline, we can find whether we can reach from the starting point to every trampoline in a total of \(\mathrm{O}(N^2)\) time by BFS (Breadth-First Searching). Instead of BFS, you may use Warshall–Floyd Algorithm.

Therefore, the problem has been solved in a total of \(\mathrm{O}(N^3 \log \mathrm{MAX})\) time, where \(\mathrm{MAX}\) is the maximum value of \(|x_i|,|y_i|\).

Beware of the upper bound of the binary search. In case of this problem, the answer can be at most \(4\times 10^9\), which do not fit into the 32-bit integer type.