2009JOI本選2 ピザ解説

解説

問題の要旨を見ればわかると思いますが、すべての注文について、「どの店が一番注文先に近いか」を求めることができればよいです。

円環なので少し実装が煩雑になりますが、これは店の位置をソートして二分探索してやればよいです。

ここからは実装上の問題ですが、円環を扱うときは、ある点からスタートして、円環を2周するように距離を記録していくと、二分探索などの処理が楽に行えることがあります。この問題でも、円環2周分の距離を記録して二分探索すれば、簡単な実装で解くことができます。