If someone can fail this solution:
Consider all lines that is pairwise combination of given points. For each line we will consider it’s top and bottom parts. For each part we solve our known calculus thing. I got WA. Someone plz tell what test fails this approach ?
I’d like to ask for tips, how to solve such hard problem, respectively how to test them. First option is to create some test cases with known results. But even for those I asked here earlier, my expected result was wrong. Only idea I found is to find mean line for every triple of points, calculate distances so I will have some upper bound. I can do that for 50 points. Typically I implement some brute force solution to get answers for random test cases, but here I have no idea how to achieve this…
I think approach to this problem is N^3logN.
Two outer loops gives us n^2. And inside it we have sorting(respect to projections to line) which is NlogN. Am I correct ?
1 Like
Why does the answer always contain two intersecting lines? Isn’t it possible to achieve better result with two parallel lines in some cases?
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.
I noticed, that both setter’s and editorialist’s solution prints printf("%.9lf\n", ans/N); is that average instead of “minimum sadness” ?
1 Like
for my inputs, your solution returns
0.66666666666666662966
0.13333333333333333148
0.82539682539682535101
Can you describe your approach more precisely? As I understood, you split the points by line. In which part are point on that line?
1 Like
Yep , u r correct. I did all possible cases. Both to bottom(1 case). Both to top(1 case). one top one bottom(2 cases). So overall 4 cases for each pair of points.
1 Like
How you googled it ? I couldn’t found any good topics
look page 23, solution to our problem ))
first:
0.535184 * x + 1 * y + -10.1315 = 0
-7.28871 * x + 1 * y + 9.95538 = 0
second:
0 * x + 1 * y + -999.667 = 0
0 * x + 1 * y + 1000 = 0
third:
0 * x + 1 * y + -999 = 0
1 * x + 0 * y + -0 = 0
1 Like
Another paper which solves a similar problem in O(N^3) can be found at http://infoscience.epfl.ch/record/164483/files/nscan3.PDF
1 Like
@kevinsogo you are correct, negative coordinates are not valid input, but once you have working algorithm, it’s not so important, but that’s why tester’s solution “fails”…
You could at least get a O(2^n) solution as described above. That is not too hard once you give a bit of thought to the problem.
The difficult part was to get it down to O(n^3). Probably the central idea was to realize the angle bisector thing. The rest of ideas used in our solutions is fairly common. When you need to bring down an infinite number of possibilities to a small finite number in geometrical setting, this method (method described in editorial) is the way to go.
1 Like
The idea of splitting point between sets SA and SB is not difficult, but I got confused because when I choose points for SA and use mean line for those, maybe some point from SB are closer to that line, but now it seems to me, that this is no problem at all…
Thanks a lot. I found bug in my calculus formula. Plus dividing by only one line will not work. It is evident for me now. It is great relief to find out where I was wrong.
