Codeforces doubt

help
1

problem :point_right: Problem - 514B - Codeforces

Can anyone explain key idea behind this solution, Particularly use of gcd.

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
 
const int N = 100005;
 
int n , X , Y;
set< pair<int , int> > h;
 
void work() {
    scanf("%d%d%d",&n,&X,&Y);
    for (int i = 0 ; i < n ; ++ i) {
        int x , y;
        scanf("%d%d",&x,&y);
        x -= X , y -= Y;
        int z = __gcd(x , y);
        h.insert(make_pair(x / z , y / z));
    }
    cout << h.size() << endl;
}
 
int main() {
    work();
    return 0;
}
2

He is simply finding slope of points wrt to (X,Y) and keeping the slope in fractional form only. So, both numr. and denom. are divided by their gcd.

If you don’t want to use gcd then see this

Code 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define lld long long int 


int main() {
	// your code goes here
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    lld t;
    //cin>>t;
    t=1;
    while(t--)
    {
        int n,x0,y0,x,y;
        cin>>n>>x0>>y0;
        
        set <double> s;
        int ptr=0;
        for(int i=0;i<n;i++)
        {
            cin>>x>>y;
            if(x!=x0)
            {
                double m=(double)1.0*(y-y0)/(x-x0);
                s.insert(m);
            }
            else
            ptr=1;
        }
        if(ptr==1)
        cout<<s.size()+1<<"\n";
        else
        cout<<s.size()<<'\n';
    }
}
3 Likes