PROBLEM LINK:
SETTER:
TESTER:
DIFFICULTY:
EASY
PREREQUISITES:
Math, STL
PROBLEM:
Given N points find how many straight line we can make such that non of them will neither parallel to X-axis nor parallel to Y-axis.
QUICK EXPLANATION:
As if n points are given so number of straight lines we can form is \binom {n}{2}.
Now we have to remove those lines which are parallel to X- axis or Y-axis.
EXPLANATION:
Now removing the lines which are parallel to X- axis or Y-axis, we just have to count the number of points having X-coordinates same and number of points having Y-coordinates same (of course independently as all points are unique). Now just subtract the lines which can be formed using these X-coordinates and Y-coordinates by applying the same formula \binom {x}{2} and \binom {y}{2}…
Note: Overlapping Straight lines are counted differently as they are formed using different set of (x,y) co-ordinates, since, we have asked about straight lines and not about the straight lines equation.
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main(){
ll t;t=1;
cin>>t;
while(t–){
ll n;
cin>>n;
map<ll,ll>mpx,mpy;
for(int i=0;i<n;i++){
ll x,y;
cin>>x>>y;
mpx[x]++;
mpy[y]++;
}
ll ans=(n*(n-1))/2;
for(auto i:mpx)
ans-=(i.second*(i.second-1))/2;
for(auto i:mpy)
ans-=(i.second*(i.second-1))/2;
cout<<ans<<"\n";
}
return 0;
}