クエリ平方分割を用いて解くことができます。

公式解説にもあるように、点の追加がなければ、クエリごとに \(O(\log Q)\) で解くことができます。

凸包を動的に管理しない場合、毎回凸包を構築する必要があり、この部分がボトルネックとなっていました。

ここで、クエリを \(D\) 回処理するごとにそれまでのクエリの点の凸包を構築しなおすとします。すると、凸包を構築する回数は \(O(\frac{Q}{D})\) 回となります。また、ソートを一回すると凸包を構築する計算量は \(O(Q)\) となります。

凸包に含まれていない \(O(D)\) 個の点は愚直に計算することで、全体の計算量は \(O(DQ+Q\log Q +\frac{Q^2}{D})\) となり、 \(D=\sqrt{Q}\) とすると、\(O(Q(\sqrt{Q}+\log Q))\) となります。