Hi I have been trying this question by another method. http://codeforces.me/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
Auto comment: topic has been updated by vacuous (previous revision, new revision, compare).
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).
you can store a line equation in its general form
Ax+By+C=0, where(don't forget to divide it by
gcd(A,B,C)and usestd::tuple)Also, don't forget that ax + by + c = 0 <=> -ax — by — c = 0