Hello all ,
I formulate my solution for this problem during the contest itself but got WA . Here is my solution i basically form equation of line using 2 point form and find the number of distinct line segment. more formally values of coefficient A , B , C are calculated.
#include using namespace std ; #define LL long long int #define ft first #define sd second #define PII pair #define MAXN 200005 #define MAXM 10000001 #define mp make_pair #define f_in(st) freopen(st,"r",stdin) #define f_out(st) freopen(st,"w",stdout) #define sc(x) scanf("%d",&x) #define scll(x) scanf("%lld",&x) #define pr(x) printf("%d\n",x) #define pb push_back #define MOD 1000000007 vector A ; vector > B ; int main(){ int N , X , Y ; sc(N) ; sc(X) ; sc(Y) ; A.resize(N+1) ; B.resize(N+1) ; for(int i=1;i<=N;i++){ sc(A[i].ft) ; sc(A[i].sd) ; } set > S ; for(int i=1;i<=N;i++){ B[i].ft.ft = A[i].ft - X; B[i].ft.sd = Y - A[i].sd ; B[i].sd = B[i].ft.sd * X + B[i].ft.ft * Y ; WA int com = __gcd(__gcd(abs(B[i].ft.ft),abs(B[i].ft.sd)),abs(B[i].sd)) ; AC int com = __gcd(__gcd((B[i].ft.ft),(B[i].ft.sd)),(B[i].sd)) ; B[i].ft.ft /= com ; B[i].ft.sd /= com ; B[i].sd /= com ; if(B[i].ft.ft < 0){ B[i].ft.ft = B[i].ft.ft * -1 ; B[i].ft.sd = B[i].ft.sd * -1 ; B[i].sd = B[i].sd * -1 ; } S.insert(B[i]) ; } cout << S.size() << endl ; return 0 ; }
I have highlighted two lines. I used above one during the contest and got WA. Later, i changed it to below one and got AC.
I know that gcd(a,b) = gcd(-a,b) = gcd(a,-b) = gcd(-a,-b) = gcd(|a|,|b|). Can anybody tell me why was i getting WA. Thanks in advance ..
__gcd doesnt have well defined behaviour for negative integers. for eg __gcd(6,-2) gives -3
Hello vignesh_m ,
I think you have not noticed that i got WA when i considered absolute of every argument and AC when i used it without absolute .