NeverSayNever's blog

By NeverSayNever, 10 years ago, In English

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 ..

  • Vote: I like it
  • -1
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

__gcd doesnt have well defined behaviour for negative integers. for eg __gcd(6,-2) gives -3

  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 .