|
|
Show all threads Hide all threads Show all messages Hide all messages | how to solve this problim with geometric way? | vnyemets | 1956. Fire Signals | 26 May 2020 12:19 | 2 | 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 | hint | ASK | 1956. Fire Signals | 24 Apr 2018 21:50 | 1 | hint ASK 24 Apr 2018 21:50 AC with 72 iterations of ternary search of line normal angle starting with [-π/2, π/2]. For some reason, [0,π] does not work. | 2 ADMINS: Very disorderly prepared statement | Vedernikoff 'Goryinyich' Sergey (HSE: АОП) | 1956. Fire Signals | 20 Jan 2014 02:59 | 1 | - Not given, whether points in the input are integers or not (in the case they are not, sample input should reflect this somehow) - Not mentioned that points in the input may coinside (from the statement it looks like they should not, but in the input they are!!!) Edited by author 20.01.2014 11:24 | WA at test case 2 | sanjeevp | 1956. Fire Signals | 18 Jun 2013 17:03 | 1 | Unable to figure out what could be test case 2. Can any one please help. | who can explain me this problem? | Mattiev Jamol | 1956. Fire Signals | 18 Jun 2013 11:15 | 6 | I couldn't understand this problem perfectly. The problem is to draw a line on the plane such that sum of distances from all points in the input to this line is minimum. And you should output this minimum number - that's all do you explain for this test and add one test to be understandable please? why the answer is 1.414214
Edited by author 16.06.2013 16:34 I'm sorry, but my explanation should be more than clear. If you don't understand - study math harder (or maybe English) In the example from the problem statement you should draw a line x - y = 0. So, the distance from (0, 0) is 0, from (0, 1) is sqrt(2)/2, from (1, 1) is 0, from (1, 0) is sqrt(2)/2. The sum of all distances is sqrt(2). I understood. thanks alot! what is the best alghoritm to solve this problem Edited by author 18.06.2013 11:58 |
|
|
|