実は、この問題を \(O(N \log N)\) 、ソート部分を除いて \(O(N)\) で解くこともできます。
まず、 \(N\) 点の重心が整数値をとるように、すべての座標を \(N\) 倍します。
その後、重心から見た \(N\) 本のベクトルの集合 \({\bf u}\) 、即ち重心を \((gx,gy)\) とすると \({\bf u_i}=(X_i-gx,Y_i-gy)\) を偏角ソートします。ただし、長さが \(0\) となったベクトル(高々 \(1\) つ)は削除するものとします。こうしてソートされたものを \({\bf v}\) とします。このとき、同じ偏角をとるベクトルが複数ある場合はその長さの昇順にソートします。

そして、この偏角ソートされたベクトルの情報 \({\bf v}\)を、次のような数列の情報に変換することを考えます。
(\(|{\bf v_1}|,{\bf v_1} \cdot {\bf v_2},{\bf v_1} \times {\bf v_2},|{\bf v_2}|,{\bf v_2} \cdot {\bf v_3},{\bf v_2} \times {\bf v_3}, \dots ,|{\bf v_N}|,{\bf v_N} \cdot {\bf v_1},{\bf v_N} \times {\bf v_1}\))
但し、 \(\cdot\) はベクトルの内積、 \(\times\) はベクトルの外積(ここでは \({\bf A}=(A_x,A_y) , {\bf B}=(B_x,B_y)\) として \({\bf A} \times {\bf B} =A_x \times B_y - A_y \times B_x\))を表します。
なお、ベクトルの長さの情報は「長さの \(2\) 乗」として整数で管理できます。

こうしてできる \(2\) つの数列に対して、片方を \(3\) 要素ずつシフトすることを繰り返してもう片方に一致させられるか判定することによってこの問題を \(O(N^2)\) で解くことができますが、この部分は Z-algorithm を使うことによって \(O(N)\) まで計算量を改善することができます。

実装例(C++)