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