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