Convex Hull TrickでDequeからPop Backするときの条件

Convex Hull TrickでDequeからPop Backするときの条件についてちょっと気になったので、考えてみました。

まずConvex Hull Trickについてですが、ここに詳しい解説があります。

要は、「y_i = a_i * x + b_iという直線集合が与えられて、あるx（複数のxが与えられる）についてy_iが最小になるiを求めよ。というクエリーを効率よく求めるためのトリックで、その応用としてDPの計算を高速化する際にも利用できることがありますよ。」
というもの。

下の3問を解いてみると、どんな感じか感覚がつかめると思います。いずれもConvex Hull Trickに気づくとDequeを使って計算量を落とすことができます。

• K-Anonymous Sequence (POJ 3709)
• Cats Transport (Codeforces Round #185)
• Land Acquisition (Usaco Mar 08 Gold)

（K-Anonymous Sequenceは蟻本にも載ってます。恐るべし、蟻本。）

で、何が気になったかというと、Dequeから直線L2をpop_backする条件です。

L1 : y = a_1 * x + b_1

L2 : y = a_2 * x + b_2

L3 : y = a_3 * b + b_3

として、今L3をDequeに入れようとしているとします。

このときL2がもう不要だといえる条件は、「L1とL3の交点 <= L1とL2の交点」です。

L1とL2の交点は、(b_2 - b_1) / (a_1 - a_2)です。L1とL3の交点は、(b_3 - b_1) / (a_1 - a_3)です。よって、

(b_2 - b_1) * (a_1 - a_3) >= (b_3 - b_1) * (a_1 - a_2)

です。

気になったのは、a_1 - a_2 = 0のときとa_1 - a_3 = 0のとき。交点がない（または直線が完全に一致する）けど、上の条件で足りているのか？

場合分けして考えてみました。

i)  a_1 = a_2のとき

(b_2 - b_1) * (a_1 - a_3) >= 0ならL2は不要となります。

a_1 >= a_3なので、b_2 >= b_1のとき不要ということになります。これは直線L2が完全にL1より上の時不要ということなので、正しいです。

ii) a_1 = a_3のとき

a_1 >= a_2 >= a_3なので、a_1 = a_2 = a_3となります。

このときは、(b_2 - b_1) * 0 >= (b_3 - b_1) * 0のときL2が不要となりますが、この条件は常になりたつので、L2は常に不要となります。これは正しい条件でしょうか？

今すでにDequeに入っているL1とL2の状態について考えてみます。L2の方がL1より下にある（またはL1とL2が一致）とすれば、L2を入れる時点でL1は消去されているはずです。ということは、L2の方がL1より上にあるということになり、常にL2はDequeから取り除いて良いということになります。

よってii)の場合も条件(b_2 - b_1) * (a_1 - a_3) >= (b_3 - b_1) * (a_1 - a_2)で足りているということになります。

そういえば今旬の「今でしょっ！」の人が、
「日常生活で、『よし、今日は直線の交点求めるか！』なんていう人がいたらヤバい」みたいなこと言ってたけど、趣味で直線の交点求めて喜ぶ人は少なからずいると思います。