Yep, sorting is to be used, however, it seems complexity of solving one case(using calculus) is large enough that it hides the complexity of sorting.
Why does the answer always contain two intersecting lines? Isnāt it possible to achieve better result with two parallel lines in some cases?
Not always result are intersecting lines, see result for my 2nd test caseā¦
If the lines are not intersecting but parallel, the rest of the section, about two perpendicular lines that define the region closer to one line etc holds - with one modification: One of the two perpendicular lines lie far on the left, so that all points are on its right. The proof and everything is valid for that case as well.
Can anyone explain me why my solution finds better answer than the authorās one?
Here is test and I guess the optimal partition looks like this. Strange thing is when I try to solve 1-line problem for these partition sets, my and authorās solutions give the same total result, but it seems like authorās solution doesnāt find this partition when it solves the test mentioned above.
My answer is 16555.8836279 and authorās is 16559.9967756. Here is my code by the way. I hope someone will explain me this.
Hi zenon! Thank you for pointing this out,
The problem here is the precision of float number. You put to much digits after the decimal point so our solution will not accurate anymore. Let say the double type can represent exactly x digits after decimal point (x depends on the range of the integer part also). Then if you use multiplication ie to calculate the projection then the input should have only x/2 digits after decimal point, Similarly, if you have product of 3 numbers somewhere in your program, then the i put should have x/3 digits after the point.
In our test cases there is about 3-4 digits after the decimal point only. Actually we should inform that in the problem statement, sorry about that.
Two consecutive projections only differ in two elements (a swap of two consecutive points), so maybe we can use only one sort and go clockwise, updating the sort order every time in O(1).