Code gives WA. Is it due to precision error or mistake in some logic?

Revision en1, by vacuous, 2015-06-22 23:21:19

Hi I have been trying this question by another method. http://mirror.codeforces.com/contest/552/problem/D

In this question, there are points in a 200X200 area and the total number of triangles(with non-zero areas) are to be calculated. Number of points is < 2000.

So instead of taking advantage of the 200X200 area, I was trying to take advantage of n<2000.

Logic -> All sets of 3 points form a triangle except when they are collinear. For lines to be collinear their slope and y-intercept needs to be same.

y=m*x + c

Since n<=2000, we can calculated m & c for every pair, store them, sort them and then compare.

I am getting WA for this logic. The test case is big and hence not entirely visible. I tried debugging the code but unable to find the bug.

One probable cause of WA , what I think , maybe the loss of precision. I am storing the slope in a double variable and comparing it afterwards. It maybe any rational number and it is rounded off differently in different cases. And while comparing they may be treated as different. Not sure, but this may be the source of the WA.

I have tried my best to keep the code simple to understand and have commented in between as well.

ideone link -> http://ideone.com/FoQyfl http://mirror.codeforces.com/contest/552/submission/11714049

Tags c++, maths, wa, precision

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English vacuous 2015-06-22 23:22:23 2 Tiny change: 'm/FoQyfl\nhttp://c' -> 'm/FoQyfl\n\nhttp://c'
en1 English vacuous 2015-06-22 23:21:19 1371 Initial revision (published)