# Codeforces doubt

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;
}

``````

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() {
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