ARC 049 B - 高橋ノルム君

• 問題
• AC

時間$t$が与えられたとき、$i$人目のノルム君の行ける範囲は$[x_i-t/c_i, x_i + t/c_i] \times [y_i -t/c_i, y_i + t/c_i]$となる。これらの$N$個の区間の共通部分が空でないことと、時間$t$内にすべてのノルム君が一点に到達できることは同値である。したがって、$t$について二分探索すればよい。

---

判定の部分を深く考えずに平衡二分木上のいもす法でやってしまったのだが、よく考えると区間の両端を保持するだけでよかった。