C++ Double Division

Revision en1, by AFN, 2016-07-04 22:15:54

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

Tags double, c++, slow

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English AFN 2016-07-04 22:23:21 33
en1 English AFN 2016-07-04 22:15:54 1342 Initial revision (published)