Yet Another Angular Sort Problem

두 점 $A_i,A_j$를 잇는 직선이 $\ell$과 만날 때 두 점의 각도 순서가 서로 바뀐다. 두 직선이 평행하지 않다면 이런 변화는 정확히 한 번 일어나고, 순열에서는 두 번호 $i,j$가 맞바뀌므로 변화량에 $2|i-j|$를 더한다. 두 점을 잇는 직선이 $\ell$과 평행하면 변화가 일어나지 않는다.

모든 쌍에 대한 $2|i-j|$의 합은

$$\frac{N(N-1)(N+1)}{3}$$

이다. $A_i=(x_i,y_i)$에 대해 $v_i=ax_i+by_i$라 두면, $A_iA_j$가 $\ell$과 평행할 필요충분조건은 $v_i=v_j$이다. 같은 $v_i$를 갖는 인덱스들을 정렬해 그 안의 $2|i-j|$ 합을 전체 합에서 빼면 된다. 시간 복잡도는 $O(N\log N)$이다.