ANTIPODAL-Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Siddhartha Tiwari
Tester: Aryan, Satyam
Editorialist: Devendra Singh

DIFFICULTY:

2522

PREREQUISITES:

Basic geometry

PROBLEM:

You are given a set of N distinct points P_1, P_2, P_3, \ldots, P_N on a 2-D plane.

A triplet (i, j, k) is called a holy triplet if

  • 1 \leq i \lt j \lt k \leq N
  • P_i, P_j and P_k are non-collinear and
  • Any two of the points P_i, P_j and P_k are antipodal points of the circle that passes through all three of them.

Two points on a circle are said to be antipodal points of the circle if they are diametrically opposite to each other.

Find the total number of holy triplets.

EXPLANATION:

An important observation

Consider a holy triplet (P_1,P_2,P_3) such that P_1 and P_3 are antipodal then P_1,P_2,P_3 lie on a semicircle as P_1 and P_3 are diametrically opposite and thus the \angle P_1P_2P_3=\pi / 2. Hence we need to count the number of triplets such that they from a right angled triangle.

The brute force solution is of the time complexity O(n^3) and even implementing a way to check if two of these points are anti-podal is not an easy task.
One way to check whether 3 points P_1,P_2,P_3 form a holy triplet is:
For now, let’s assume these points are not collinear. We
can find out whether the angle between the lines P_1-P_2 and P_1-P_3 is \pi / 2 radians or not. To check this we have to multiply the slopes of these two lines and check if it equal to -1 or not. If it is, then (P_2, P_3) will be antipodal. If it’s not check the same condition for other pairs of lines,
namely (P_2-P_3 and P_2-P_1) and (P_1-P_2 and P_1-P_3). If one of these conditions is true then we have a holy triplet.
Now, this solution can be reduced to O(n^2log(n)). To do that, we have to fix the point that will act as the point other than the two antipodal points in any triplet. Let fixed point be P_1 and we are searching for all pairs (P_2, P_3) in the set of points which satisfy the given requirement. This can be done in O(nlog(n)). Create an array of pairs of integers A[1...n]. A_i
is defined as A_i(a, b), where a / b is the slope of the line formed by joining the fixed point P_1 and P_i and gcd(a, b) = 1. Now we can say that two points P_i and P_j are antipodal with P_1 as the
third point, if (A[i].a / A[i].b) * (A[j].a / A[j].b) = -1 or A[j].a / A[j].b = -A[i].b / A[i].a. And since
gcd(A[j].a, A[j].b) = gcd(A[i].a, A[i].b) = 1, we can safely say that A[j].a = -A[i].b and A[j].b = A[i].a
OR A[j].a = A[i].b and A[j].b = -A[i].a. Now, we can use a map to store these pairs. Now iterate on the array of points taking P_i as a fixed point and create the array A for each point as shown above. Now iterate for point P_2 and check if there exists a point P_3 antipodal to it. If yes add it to the answer.

TIME COMPLEXITY:

O(N^2log(N)) for each test case.

SOLUTION:

Setter's Solution
#include <bits/stdc++.h>

using namespace std;

using LL = long long;

class Point {
	public:
		LL x, y;
		Point(LL x, LL y) {
			this->x = x;
			this->y = y;
		}
		Point() {
			this->x = 0;
			this->y = 0;
		}

		string toString() {
			return "{" + to_string(x) + "; " + to_string(y) + "}";
		}
};

class Slope {
	public:
		LL numerator, denominator;
		Slope(Point first, Point second) {
			numerator = second.y - first.y;
			denominator = second.x - first.x;
			LL sign = 1, gcd = 1;

			if (numerator * denominator < 0)
				sign = -1;

			numerator = abs(numerator);
			denominator = abs(denominator);

			if (numerator == 0 || denominator == 0)
				numerator *= sign;
			else {
				gcd = __gcd(numerator, denominator);
				numerator /= gcd;
				denominator /= gcd;
			}

			numerator *= sign;
		}


		Slope(LL numerator, LL denominator) {
			this->numerator = numerator;
			this->denominator = denominator;

			LL sign = 1;
			if (this->numerator * this->denominator < 0)
				sign = -1;
			
			this->numerator = abs(this->numerator);
			this->denominator = abs(this->denominator);
			
			this->numerator *= sign;
		}

		Slope() {
			this->numerator = 0;
			this->denominator = 0;
		}

		Slope getPerpendicular() {
			return Slope(-denominator, numerator);
		}
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T;
	cin >> T;
	while (T--) {
		int N;
		cin >> N;
		vector<Point> points(N);
		for (int i = 0; i < N; i++)
			cin >> points[i].x >> points[i].y;
	
		// fix the non-antipodal point in the triplet, and search for antipodal points around it.
		int ans = 0;
		for (int i = 0; i < N; i++) {
			map<pair<LL, LL>, int> count;
			vector<Slope> slopes(N);
			int zero = 0, infinity = 0;
			for (int j = 0; j < N; j++) {
				if (i == j) continue;
				slopes[j] = Slope(points[i], points[j]);
				pair<LL, LL> nPair(slopes[j].numerator, slopes[j].denominator);
				if (count.find(nPair) == count.end())
					count.insert({nPair, 1});
				else
					count[nPair]++;

				if (slopes[j].numerator == 0) zero++;
				if (slopes[j].denominator == 0) infinity++;
			}

			for (int j = 0; j < N; j++) {
				if (i == j) continue;

				if (slopes[j].numerator == 0) {
					ans += infinity;
					continue;
				}
				else if (slopes[j].denominator == 0) {
					ans += zero;
					continue;
				}

				Slope perpendicular = slopes[j].getPerpendicular();
				pair<LL, LL> nPair(perpendicular.numerator, perpendicular.denominator);
			
				if (count.find(nPair) != count.end())
					ans += count[nPair];
			}
		}
		cout << ans / 2 << "\n";
	}

	return 0;
}
Tester-1's Solution
/* in the name of Anton */

/*
  Compete against Yourself.
  Author - Aryan (@aryanc403)
  Atcoder library - https://atcoder.github.io/ac-library/production/document_en/
*/

#ifdef ARYANC403
    #include <header.h>
#else
    #pragma GCC optimize ("Ofast")
    #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
    //#pragma GCC optimize ("-ffloat-store")
    #include<bits/stdc++.h>
    #define dbg(args...) 42;
#endif

// y_combinator from @neal template https://codeforces.com/contest/1553/submission/123849801
// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0200r0.html
template<class Fun> class y_combinator_result {
    Fun fun_;
public:
    template<class T> explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
    template<class ...Args> decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward<Args>(args)...); }
};
template<class Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); }

using namespace std;
#define fo(i,n)   for(i=0;i<(n);++i)
#define repA(i,j,n)   for(i=(j);i<=(n);++i)
#define repD(i,j,n)   for(i=(j);i>=(n);--i)
#define all(x) begin(x), end(x)
#define sz(x) ((lli)(x).size())
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define endl "\n"

typedef long long int lli;
typedef long double mytype;
typedef pair<lli,lli> ii;
typedef vector<ii> vii;
typedef vector<lli> vi;

const auto start_time = std::chrono::high_resolution_clock::now();
void aryanc403()
{
#ifdef ARYANC403
auto end_time = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> diff = end_time-start_time;
    cerr<<"Time Taken : "<<diff.count()<<"\n";
#endif
}

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;
            }
            assert(l<=x&&x<=r);
            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,' ');
}

void readEOF(){
    assert(getchar()==EOF);
}

vi readVectorInt(int n,lli l,lli r){
    vi a(n);
    for(int i=0;i<n-1;++i)
        a[i]=readIntSp(l,r);
    a[n-1]=readIntLn(l,r);
    return a;
}

bool isBinaryString(const string s){
    for(auto x:s){
        if('0'<=x&&x<='1')
            continue;
        return false;
    }
    return true;
}

// #include<atcoder/dsu>
// vector<vi> readTree(const int n){
//     vector<vi> e(n);
//     atcoder::dsu d(n);
//     for(lli i=1;i<n;++i){
//         const lli u=readIntSp(1,n)-1;
//         const lli v=readIntLn(1,n)-1;
//         e[u].pb(v);
//         e[v].pb(u);
//         d.merge(u,v);
//     }
//     assert(d.size(0)==n);
//     return e;
// }

const lli INF = 0xFFFFFFFFFFFFFFFL;

lli seed;
mt19937 rng(seed=chrono::steady_clock::now().time_since_epoch().count());
inline lli rnd(lli l=0,lli r=INF)
{return uniform_int_distribution<lli>(l,r)(rng);}

class CMP
{public:
bool operator()(ii a , ii b) //For min priority_queue .
{    return ! ( a.X < b.X || ( a.X==b.X && a.Y <= b.Y ));   }};

void add( map<lli,lli> &m, lli x,lli cnt=1)
{
    auto jt=m.find(x);
    if(jt==m.end())         m.insert({x,cnt});
    else                    jt->Y+=cnt;
}

void del( map<lli,lli> &m, lli x,lli cnt=1)
{
    auto jt=m.find(x);
    if(jt->Y<=cnt)            m.erase(jt);
    else                      jt->Y-=cnt;
}

bool cmp(const ii &a,const ii &b)
{
    return a.X<b.X||(a.X==b.X&&a.Y<b.Y);
}

const lli mod = 1000000007L;
// const lli maxN = 1000000007L;

    lli T,n,i,j,k,in,cnt,l,r,u,v,x,y;
    lli m;
    string s;
    vi a;
    //priority_queue < ii , vector < ii > , CMP > pq;// min priority_queue .

ii reduce(lli x,lli y){
    lli g=__gcd(abs(x),abs(y));

    x/=g;y/=g;
    if(y<0){
        x*=-1;
        y*=-1;
    }
    // if(x==0&&y<0)
    //     y*=-1;
    return {x,y};
}

int main(void) {
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    // freopen("txt.in", "r", stdin);
    // freopen("txt.out", "w", stdout);
// cout<<std::fixed<<std::setprecision(35);
T=readIntLn(1,10);
lli sumN = 2000;
while(T--)
{

    n=readIntLn(3,sumN);
    sumN-=n;
    vii a(n);
    for(auto &x:a){
        auto b=readVectorInt(2,-1e9,1e9);
        x.X=b[0];
        x.Y=b[1];
    }
    sort(all(a));
    (a).erase(unique(all(a)),(a).end());
    assert(sz(a)==n);

    lli ans=0;
    for(int deg90=0;deg90<n;++deg90){
        map<ii,lli> count;
        lli x=0,y=0;
        for(int j=0;j<n;j++){
            if(deg90==j)
                continue;
            auto oth=reduce(-(a[deg90].X-a[j].X),a[deg90].Y-a[j].Y);
            if(oth.X==0)
                x++;
            if(oth.Y==0)
                y++;
            if(oth.X==0||oth.Y==0)
                continue;
            ans+=count[oth];
            auto cur=reduce(a[deg90].Y-a[j].Y,a[deg90].X-a[j].X);
            count[cur]++;
        }
        ans+=x*y;
    }
    cout<<ans<<endl;
}   aryanc403();
    readEOF();
    return 0;
}

Tester-2's Solution
#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=readIntLn(3,2000);
    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++){
        x[i]=readIntSp(-MAX,MAX); y[i]=readIntLn(-MAX,MAX);
        check.insert({x[i],y[i]}); 
    }
    assert(check.size()==n); 
    for(ll i=1;i<=n;i++){
        map<pair<ll,ll>,ll> freq; 
        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;
            }
            freq[{num,denom}]++;
            ll l=-denom,r=num;
            if(r<0){
                r=-r,l=-l;
            }
            ans+=freq[{l,r}]; 
        }  
    }
    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=readIntLn(1,10); 
    while(test_cases--){
        solve();
    }
    assert(getchar()==-1);
    assert(tes_sum<=2000);
    return 0;
}

2 Likes

#include
using namespace std;

int check_collinear(int x1, int y1, int x2, int y2, int x3, int y3){
if ((y3 - y2)*(x2 - x1)==(y2 - y1) * (x3 - x2))
return 0;
else
return 1;
}

int main() {
// your code goes here
long long int t; cin>>t;
while(t–){
long int num;
cin>>num;
long long int a[num];
long long int b[num];
long long int c=0;
for(long long int i=0;i<num;i++){
cin>>a[i];
cin>>b[i];

    }
     
  for(int i=0;i<num-2;i++)
  {
      for(int j=i+1;j<num-1;j++)
  {
        for(int k=j+1;k<num;k++)
  {
      c=c+check_collinear(a[i],b[i],a[j],b[j],a[k],b[k]);
  }
  }
  }
  cout<<c<<endl;
}
return 0;

}

CAN YOU PLS TELL ME WHATS WRONG IN MY SOLUTION

I have done this in O(N^2) in a simple way .
https://www.codechef.com/viewsolution/63622353

@cu_21bcs7757
You are only checking collinearity . But you also have to check whether they form a right angle triangle on not .

1 Like

Why is it mention in the ques?

https://www.codechef.com/viewsolution/63557307
can anyone check my code and let me know why i got TLE, i think my code has O(n2) complexity

Hey Can you explain what are you trying to do

Hey can someone tell me whats wrong with my approach i am doing the same this as in editorial
Here is my code

#include<bits/stdc++.h>
using namespace std;
#define pp pair<long long,long long>
#define ll long long

double getslope(pp &a,pp &b){
   
   double x=a.first - b.first;
   double y=a.second - b.second;
   if(x!=0){
       return y/x;
   }else{
       return INFINITY;
   }
   

}
int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        pp points[n];
        
        for(int i=0;i<n;i++){
            ll x,y;
            cin>>x>>y;
            points[i]=make_pair(x,y);
            
        }
        

        unordered_map<double,ll> infinte;
        unordered_map<double,unordered_map<ll,ll>*> m;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(i!=j){
                double slope=getslope(points[i],points[j]);
                // cout<<slope<<" "<<i<<" "<<j<<endl;

                if(slope==INFINITY){
                    infinte[i]++;
                }else{
                // double slope =i;
                if(m.find(slope)==m.end()){
                    unordered_map<ll,ll>* temp = new unordered_map<ll,ll>();
                    (*temp)[i]++;
                    m[slope]=temp;
                }
                else{
                    (*m[slope])[i]++;
                }
                }
                }
            }
        }
       ll count=0;
      for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(i!=j){
                double slope=getslope(points[i],points[j]);
                // double slope =i;
                if(slope==INFINITY){
                    if(m.find(0)!=m.end()){
                        // cout<<1<<endl;
                        auto it=m[0];
                        if(it->find(j)!=it->end()){
                            count+=it->at(j);
                        }
                        
                    }
                }else if(slope==0){
                    if(infinte.find(j)!=infinte.end()){
                        count+=infinte[j];
                    }
                }
                else{
                    double temp=-1.0/slope;
                    if(m.find(temp)!=m.end()){
                        auto it=m[temp];
                        // cout<<2<<endl;
                        if(it->find(j)!=it->end()){
                            count+=it->at(j);
                        }
                         
                    }
                }
                }
            }
        }
        for(auto it:m){
            delete it.second;
        }
        cout<<count<<endl;
        


    }


}

In question it is mentioned that we have to find antipodal points , which indirectly refers to the points forming right angle triangle .

@shivam_2701
The goal is to find total number of right angle triangle . So i iterate through all points(say x) and find all the possible right angle triangle such that x is the point where they form 90degree . To do that simply iterate through all the other points except x , store the current slope and add the number of slope perpendicular to it .

@aadarshsinha

For every line segment formed by two points:

  1. Store the current angle made by it with the x-axis.
  2. If found an angle perpendicular to the current angle, that means we found a right angle triangle.

Is this the intuition?

What happens when two line segments are perpendicular but do not have a common point?

1 Like

Nvm, the first point is fixed, nice solution.

Are you sure about the time complexity?

Hey @adithya5768 :wave:
This is an n^3 solution which will lead you to TLE and you are only checking that the points are collinear.

I am not sure about the time complexity of atan() . Though I have searched in google , but i didnt got any results .
I think we can even remove the atan() . Instead of storing angle we can even store the slope .

You cannot use a global map. It should be inside the first for loop because it’s entries are only valid for the corresponding non-antipodal point.

For each non-antipodal point, I am trying to store unit vector formed with other points in the map and find unit vectors perpendicular to the current unit vector in the map but I am getting a few WA. Can anyone help me with this?

https://www.codechef.com/viewsolution/63656890

It has written in the editorial that searching of (P2,P3) is O(n) order. Its seems to me that it is O(n^2). Can someone explain this how?

std::map in C++ is implemented as \text{Red-Black tree}. Search and Insertion have logarithmic time complexity. So, the time complexity of your code is not O(N^2). It is O(N^2\log{N})

1 Like

In the solution where are you checking if the points x is the part of the line with perpendicular slope