問題

$xy$ 平面上に $N$ 個の点がある．4 つの点を選んで四角形を作るとき，その面積を最大化せよ．

$O(N^3)$ 解法

$N$ 個の点の凸包上の点を反時計回りに $C_1,C_2,\ldots,C_M$ とします( $M$ は凸包上の点の数)．このとき， $M=3$ の場合は，（凸包の 3 点） + (それ以外の 1 点) で四角形を作るのが最適です．よって， $O(N)$ かけてすべての候補を調べればよいです．

以下では， $M\geq 4$ とします．このとき，面積が最大となるような四角形の頂点は全て凸包上にあります（凸包上に無い点を含むとき，適切に凸包上の点に変更することで面積を大きくできます）．

四角形の対角線をなす点を $C_L,C_R(1\leq L,L+2\leq R\leq M)$ で固定します．このとき，残りの二点の候補は $C_i (L\lt i\lt R)$ と $C_j(R\lt j\lt L+M)$ （ $C_i$ と $C_{i+M}$ は同一視する）になるので， $\triangle C_LC_RC_i,\triangle C_RC_LC_j$ の面積が最大になる点それぞれを $O(N)$ で調べればよいです．対角線の候補は $O(N^2)$ 通りありますから，全体で $O(N^3)$ で解くことができました．

$O(N^2 \log N)$ 解法

対角線をなす 2 点 $C_L,C_R$ を固定したとき， $\triangle C_LC_RC_i,\triangle C_RC_LC_j$ の面積はそれぞれ $i,j$ に関して凸になっています．よって三分探索をすることにより，各対角線ごとに $O(\log N)$ で求めることができます．

$O(N^2)$ 解法

$C_L$ を固定します．このとき， $\triangle C_LC_RC_i$ が最大となる $i$ は $R$ に関して単調増加になっています．よって尺取り法の要領により，各 $L$ に対して，すべての $R$ に対する $\triangle C_LC_RC_i$ の最大値を $O(N)$ で求めることができます．

とりゐのブログ

MMA Contest 015 J : Maximum Quadrilateral

問題

$O(N^3)$ 解法

$O(N^2 \log N)$ 解法

$O(N^2)$ 解法