Codeforces Hello 2020 E. New Year and Castle Construction

問題概要

座標平面上に $n$ 個の点があり、 $i$ 番目の点の座標は $(x_{i}, y_{i})$ である。これら $n$ 個の点からなる集合を $s$ と表記する。全ての点は相異なり、どの3点をとってもそれらが一直線上に存在することはない。

点 $p\in s$ のスコア $f(p)$ を、「 $s$ に含まれる4点の選び方のうち、その4点を結ぶ四角形が点 $p$ を内部（辺上は除く）に含むものの個数」と定義する。全ての点 $p\in s$ についてのスコア $f(p)$ の総和を求めよ。

制約

$5 \le n \le 2500$
$-10^{9} \le x_{i}, y_{i} \le 10^{9}$
全ての点は相異なり、どの3点をとってもそれらが一直線上に存在することはない

解法

点 $p$ を全通り試します。点 $p$ が原点となるよう、その他の $n-1$ 個の点の座標を平行移動します。

$n-1$ 個の点から4点を選ぶ選び方のうち、四角形が点 $p$ を内部に含まないようなものを数えて $_{n-1}C_{4}$ から引くことにします。これはどのように判定できるでしょうか。

f:id:betrue12:20200105135727p:plain

この図のように、4点を偏角の順に並べたときに、1点目→2点目、2点目→3点目、3点目→4点目、4点目→周回後の1点目、のいずれかの点間において偏角が180度以上進んでいることが、四角形が原点を内部に含まない必要十分条件になります。

ここで3点が一直線上にないという制約により、「偏角差がちょうど180度」という状況はあり得ないことに注意します。もし偏角差がちょうど180度である2点がある場合、原点 $p$ を含めて3点が一直線上に並んでしまうからです。同様の理由で、偏角が等しい2点が存在することもありません。

このことから、先ほどの4つの点間のうち偏角差が180度以上である（180度を超える）ものは高々1つであることが分かります。これによって重複カウントを防ぐことができます。

具体的には、 $n-1$ 個の点を偏角でソートし、2周分の要素を確保しておきます。1点目を順番に試し、「今1点目としている点から見て、偏角が180度以上進んでいるものはどの点以降か」を尺取り法などで管理します。偏角が180度以上進んでいる点が $k$ 個ある場合、この中から残りの3個を選ぶことで点 $p$ を内部に含まない四角形ができるので、 $_{k}C_{3}$ を答えから引いていきます。

点 $p$ を全通り試して、それぞれについて残りの点のソートを行うので、全体計算量 $O(n^{2}\log n)$ となります。

誤差に影響されない偏角の扱い方

座標の値が大きいので、偏角を求めたり180度の境界を求めるところで誤差によって答えがずれてしまい大変でした。全体的に long double の精度を確保することで通ったようですが、極力小数を用いないような処理方法を考えてみます。

まず整数座標の点を偏角でソートする場合は、偏角を std::atan2 などで求めるのではなく「符号付き面積」を用いることができます。

参考：符号のある面積

原点を $O = (0, 0)$ とし、点 $A = (a_{1}, a_{2})$ と点 $B = (b_{1}, b_{2})$ と原点の3点が相異なるとします。三角形 $OAB$ の符号付き面積は $\frac{1}{2}(a_{1}b_{2} - b_{1}a_{2})$ と定義されます。これは一般的な座標平面において $O, A, B$ が反時計回りに結ばれている時に正、時計回りに結ばれている時に負となります。

この値は、点 $A, B$ の原点からの距離をそれぞれ $|A|, |B|$ 、偏角をそれぞれ $\theta_{A}, \theta_{B}$ としたときに、 $\frac{1}{2}|a||b|\sin(\theta_{B} - \theta_{A})$ と一致します。つまり $|A|, |B|$ が正であれば $(a_{1}b_{2} - b_{1}a_{2})$ と $\sin(\theta_{B} - \theta_{A})$ は符号が一致することになります。

これを利用して偏角ソートができます。まず偏角の範囲をどう取るかを決めましょう。例えば度数法で $\lbrack 0, 360)$ であるとします。

ソートしたい点を、まず4象限に分けます。それぞれの象限の内部においては、偏角の差は90度以下であることが保証されます。このとき同じ象限に含まれる2点 $A = (a_{1}, a_{2})$ と2点 $B = (b_{1}, b_{2})$ について、 $(a_{1}b_{2} - b_{1}a_{2})$ と $\sin(\theta_{B} - \theta_{A})$ の符号が一致し、偏角差が90度以下であることから $(\theta_{B} - \theta_{A})$ とも符号が一致します。つまり座標値が整数であれば、比較関数において $(a_{1}b_{2} - b_{1}a_{2})$ の符号を確認することで誤差なく象限内での偏角ソートを行うことができます。あとは決めた偏角の範囲に合うように象限ごとに並べれば偏角ソート完了です。