Hey guys I wanted to share with you something I discovered.
I was checking contests I took part in last year and stumbled into round 308 Div2. Problem D: This
This problem could be solved by simple O(n^3) by just picking all triplets and see if they make a triangle.
Well last year I calculated m1 = (y[k] — y[j]) / (x[k] — x[j]) and calculated m2 = (y[j] — y[i]) / (x[j] — x[i]) as doubles and if (m1 == m2) then it's triangle.
Looking at the constraints n <= 2000 so this answer should pass in the problem's time limit which is 4 seconds. But I got TLE.
This year while checking my previous solution, I decided to just convert the equation like this:
=> m1 = m2
=> (y[k] — y[j]) / (x[k] — x[j]) = (y[j] — y[i]) / (x[j] — x[i])
=> (y[k] — y[j]) * (x[j] — x[i]) = (y[j] — y[i]) * (x[k] — x[j])
So now both l1 and l2 could be calculated as integers, I did this and AC. Wow.
Seems like double division in C++ takes time, while multiplication as integers is faster, that's why I got AC.
Previous (TLE) Submission: Submission 18887929
Current (AC) Submission: Submission 18887986
This problem could be solved by simple O(n^3) ...
Expected solution is O(n^2 * logn).
You can notice that time limit is 4 seconds so O(n^3) should pass. And it actually passed.
From editorial : I am sorry, that O(n^3 / 6) solutions passed, my solution with O(n^3 / 6) didn't pass before the contest, so I decided, that TL 4 sec is good(it was for Java TL).
But O(n^3) solutions did actually pass, and editorial's solution is not the only one there. And I'm not discussing the solution I'm just discussing that double division got TLE while integer multiplication passed.