I really like geometric problems. The problem can be solved using LP, PCA, analysis. But how to apply computational geometry (convex hull) to the problem?

The optimal line goes through two points; it's not some arbitrary line. This could lead to O(N^3) solution if you enumerate every of N(N-1)/2 lines and compute the distance in O(N). A better solution is doing two-pointers optimization for every point. For each point you have to sort all the other points according to their polar angle with the fixed point; and then computation of O(N) lines for a fixed endpoint takes linear time with two pointers. Complexity of this solution is O(N^2 log N). Just recall that point-line distance is given by the formula abs(a*X+b*Y)/sqrt(a*a+b*b) (as one of endpoints is treated as an origin there is no constant term in abs()). So you could group points (X,Y) into two groups: those that have a positive sign of (a*X+b*Y) and those that have a negative one — this is precisely what you need two pointers for. Then the answer for each line will be computed as (a*sumX_PositiveGroup + b*sumY_PositiveGroup - a*sumX_NegativeGroup - b*sumY_NegativeGroup)/sqrt(a*a+b*b).

Edited by author 26.05.2020 12:21