ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
back to board

Discussion of Problem 1956. Fire Signals

how to solve this problim with geometric way?
Posted by vnyemets 24 May 2020 19:28
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?
Re: how to solve this problim with geometric way?
Posted by Gilles Deleuze 26 May 2020 12:19
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