概要
解法
LGV 公式を使います。
参考：ABC 216 H 解説（https://atcoder.jp/contests/abc216/editorial/2561）
可能な線分すべてを考えてしまうと、線分に交差が生じる場合があります（サンプル 3）。しかし、$x$ 座標が相異なるという制約のおかげで、その可能性は初手以外にはありません。実際、$x$ 座標の異なる $2$ 点から出る線分は端点以外で交差しないことが確かめられます。例えば、左下の点 $A$ と右上の点 $B$ から出る線分が交差するならば、$A$ その行き先は $y$ 座標が $A$ 以下であることが確定することから示すことができます。
よって、左端の点の接続先を固定してしまえば、LGV 公式を適用することが可能になります。$N^3$ 回計算することで、全体として $O(N^3(NM+N^3))$ 時間などで解くことができます。
