➤ Problem Link : CHASE
👉 Hint : Use unordered map
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
pair<int,int> arr[2201];
bool comp(pair<int,int> a,pair<int,int> b)
{
double l,f;
int ax=a.first;
int ay=a.second;
int bx=b.first;
int by=b.second;
if(ax==0)
l=INT_MAX;
else
l=(double)ay/ax;
if(bx==0)
f=INT_MAX;
else
f=(double)by/bx;
return l<=f;
}
bool compxy(pair<int,int> a,pair<int,int> b)
{
int ax=a.first;
int ay=a.second;
int bx=b.first;
int by=b.second;
if(ax!=bx)
return ax<bx;
return ay<by;
}
int main()
{
int t;
cin>>t;
unordered_map<double,int> um;
while(t--)
{
int ans=0;
int k;
cin>>k;
for(int i=0;i<k;i++)
cin>>arr[i].first>>arr[i].second;
sort(arr,arr+k,compxy);
for(int i=0;i<k;i++)
{
int xi=arr[i].first;
int yi=arr[i].second;
um.clear();
for(int j=i+1;j<k;j++)
{
if(j!=i)
{
double l;
int x=arr[j].first;
int y=arr[j].second;
if(x-xi!=0)
l=(double)(y-yi)/(x-xi);
else
l=INT_MAX;
um[l]++;
}
}
for(auto it=um.begin();it!=um.end();it++)
ans=max(ans,(*it).second);
}
cout<<ans<<endl;
}
}
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!
I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.