Hey why are you checking the second angle in different way
double m1 = atan(1.0 * (y[i] - y[j]) / (x[i] - x[j])) * 180 / PI;
double m2 = atan(1.0 * (x[j] - x[i]) / (y[i] - y[j])) * 180 / PI;
The first angle i.e m1 is angle with X axis and what about second one i.e m2 ??
@pratik_nextrix @shivam_2701
Here m1 is the current slope between ith and jth point . m[m1]++ implies i am incrementing the count of this slope .
m2 is the slope perpendicular to m1 . ans+=m[m2] implies that i am adding the count of points which have slope as m2 . Because they will form right angle triangle
Try to do dry run for better understanding .
@adithya5768 Hey I have changed this code to use a vector now can you please help me i am getting a runtime error
https://www.codechef.com/viewsolution/63692584
Here is the link of the submission
@shivam_2701 Are you aware that your code could use up to O(n^3) space?
For each line segment, you are creating a vector of size n. There could be n^2 line segments.
There probably is so much unnecessary information being stored in memory.
I do not know if that is the limit for memory usage in this platform.
Besides, like I mentioned before, you do NOT need to use a “global” map. Just declare a map inside the first for loop and use it inside the second for loop.
Thank you brother I was able to correct my code and now it passes all he test case
my final code
https://www.codechef.com/viewsolution/63730641
1 Like
For this data, I test several diffrent AC code(include the author and the tester), the answer are diffrent, who are corrected?
1
10
0 0
0 1
1 0
1 1
2 2
1 2
2 1
3 3
2 3
3 2
Hey @huas_huah ,
For your test case Testers 2 Solution is giving wrong answer reason is it is not counting the numerator and denominator pairs that are 0. You can go through the modified code to understand properly.
#include <bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
#define debug(x) cerr<<#x<<" "; _print(x); cerr<<nline;
#else
#define debug(x);
#endif
#define ll int
/*
------------------------Input Checker----------------------------------
*/
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(1 == 0);
}
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
/*
------------------------Main code starts here----------------------------------
*/
ll MAX=1e9;
ll tes_sum=0;
void solve(){
ll n;
cin>>n;
tes_sum+=n;
vector<ll> x(n+5),y(n+5);
ll ans=0;
set<pair<ll,ll>> check;
for(ll i=1;i<=n;i++){
cin>>x[i]>>y[i];
check.insert({x[i],y[i]});
}
assert(check.size()==n);
for(ll i=1;i<=n;i++){
map<pair<ll,ll>,ll> freq;
int X = 0,Y = 0;
for(ll j=1;j<=n;j++){
if(i==j){
continue;
}
ll num=y[i]-y[j],denom=x[i]-x[j];
ll g=__gcd(num,denom);
num/=g; denom/=g;
if(denom<0){
denom=-denom,num=-num;
}
if(num == 0) X++;
if(denom == 0) Y++;
if(!num || !denom) continue;
freq[{num,denom}]++;
ll l=-denom,r=num;
if(r<0){
r=-r,l=-l;
}
ans+=freq[{l,r}];
}
ans += X*Y;
}
cout<<ans<<"\n";
return;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
freopen("error.txt", "w", stderr);
#endif
ll test_cases;
cin>>test_cases;
while(test_cases--){
solve();
}
assert(getchar()==-1);
assert(tes_sum<=2000);
return 0;
}
So, the test cases were weak, right?