この解説では \(2\) 直線 \(\ell, m\) の交点を \(I_{\ell, m}\) で表すことにします。

はじめに、平行な直線がない場合を考えます。

このとき、凸包の頂点となりうるのは「直線群を傾きでソートしたときに隣り合う \(2\) 直線の交点」であることが言えます。 これは、傾きの順に並ぶ \(4\) つの直線 \(m_1, m_2, m_3, m_4\) について、適当な場合分けによって \(I_{m_1, m_3}\) が (\(3\) 直線が同一の点で交わる場合を除いて) 凸包の頂点に含まれないことから従います。

ゆえに、このケースでは凸包の頂点の候補を \(N\) 点に減らせます。

次に、平行な直線を含む場合です。

直線 \(m_1, m_2, m_3\) が平行でこの順に並び、直線 \(\ell\) がこれらと交わるとき、 \(I_{\ell, m_2}\) は \(I_{\ell, m_1}\) と \(I_{\ell, m_3}\) の間に位置するため \(I_{\ell, m_2}\) は凸包の頂点になりえません。 したがって、平行な直線のうち凸包に影響を与えるのは端にある高々 \(2\) 直線です。

以上より、平行な直線を適切に処理したのち偏角ソートを行うことで、凸包の頂点の候補を高々 \(4N\) 点に絞ることができます。 あとはこれらの点に対する凸包を求めることで元の問題が解けます。 計算量は \(O(N \log{N})\) time です。