vacuous's blog

Code gives WA. Is it due to precision error or mistake in some logic?
By vacuous, history, 9 years ago, In English

Hi I have been trying this question by another method. http://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://codeforces.com/contest/552/submission/11714049

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by vacuous (previous revision, new revision, compare).

→ Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Yes, I had problems with precision on this problem too. One thing that helped me was adding an epsilon to my comparisons (if the absolute of the difference between two slopes was less than 10^-9 then I counted them as equal).

→ Reply
»
9 years ago, # |
  Vote: I like it +6 Vote: I do not like it

you can store a line equation in its general form Ax+By+C=0, where

A = y1 - y2
B = x2 - x1
C = x1*y2 - x2*y1

(don't forget to divide it by gcd(A,B,C) and use std::tuple)

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Also, don't forget that ax + by + c = 0 <=> -ax — by — c = 0

    → Reply