The idea is to try every segment (i.e. place the line so that it overlaps the segment, the rotate it by a little bit). We can show that every line in the plane can be reduced to one of those O(N^2) lines above.

We now want to process each line in constant time or logarithmic time. To iterate through all these configurations efficiently, fix one point, then sort the other points by angle around that one point. Then, rotate around the endpoints, keeping two pointers at a 180 degree angle. All we need to do is find way to update the cost of the segments we cut in constant time. The cost is defined as (x_1 — x_2)^2 + (y_1 — y_2)^2, and expanding gives x_1^2 — 2x_1x_2 + x_2^2 + y_1^2 — 2y_1y_2 + y_2^2.

For now, let's focus on only x-coordinates. If L2 is the sum of squares of x coordinates on the left side of the line, L1 is the sum of x coordinates, and L0 is the number of points (similarly define R2, R1, R0 for right side), then our total cost is L2 * R0 — 2 * L1 * R1 + L0 * R2. Similarly, we can get the y coordinate score like this as well and just add the two together.

Now, updating these sums is relatively simple as we're rotating around, and rotating around each point will take O(N) time total. Since we need to sort before, the total running time of this solution should be O(N^2 log N)