[AtCoder] diverta 2019 Programming Contest 2 B – Picking Up

問題

方針

\( p, q \) を固定して全探索を行う

ボールの各座標を位置ベクトルとして、 \( \vec{v}_i = (x_i, y_i) \) と表すことにします。\( p, q \) の候補は、任意の二つの位置ベクトルの差分として、\( \vec{u}_{i, j} = (x_i – x_j, y_i – y_j) \) とします。これは、\( N \) 個から \( 2 \) 個選ぶ組み合わせに、向きを考慮して、\( N(N – 1) \) 通りあることになります。 なぜこのような候補になるかというと、これ以外の \( p, q\) の値は、コストが \( 0 \) になる可能性がないからです。

また、コストが掛からないときは、どういうことかというと、

\[ \vec{v}_i =\vec{v}_j + \vec{u}_{k, l} \ (i \neq j \wedge k \neq l)\]

を満たすということです。したがって、\(\vec{u}_{k, l} \) と \( \vec{v}_i, \vec{v}_j \) の全探索行うので、\( 4 \) 重ループの計算を行えば良いです。ここで、注意する点は同じ座標のボールは存在しないことから、\( \vec{u}_{k, l} \) と \( \vec{u}_j \) を固定したとき、上記の式を満たす \( \vec{v}_i \) は最大でも一つしかありません。

コード

提出したコード

全探索