Yet Another Angular Sort Problem

The angular order of $A_i$ and $A_j$ swaps when the line through them intersects $\ell$. If the two lines are not parallel, this happens exactly once and swaps the two indices in the permutation, contributing $2|i-j|$. If their line is parallel to $\ell$, no such change occurs.

The sum of $2|i-j|$ over all pairs is

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

For $A_i=(x_i,y_i)$, set . The line is parallel to exactly when . Sort points by , compute the sum of inside every equal-value group, and subtract it from the total. The time complexity is .