Pairs with same Manhattan and Euclidean distance | C ++ implementation of the above approach ; Function to return the number of non coincident pairs of points with manhattan distance equal to euclidean distance ; To store frequency of all distinct Xi ; To store Frequency of all distinct Yi ; To store Frequency of all distinct points ( Xi , Yi ) ; ; Hash xi coordinate ; Hash yi coordinate ; Hash the point ( xi , yi ) ; find pairs with same Xi ; calculate ( ( xFrequency ) C2 ) ; find pairs with same Yi ; calculate ( ( yFrequency ) C2 ) ; find pairs with same ( Xi , Yi ) ; calculate ( ( xyFrequency ) C2 ) ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int findManhattanEuclidPair ( pair < int , int > arr [ ] , int n ) { map < int , int > X ; map < int , int > Y ; map < pair < int , int > , int > XY ; for ( int i = 0 ; i < n ; i ++ ) { int xi = arr [ i ] . first ; int yi = arr [ i ] . second ; X [ xi ] ++ ; Y [ yi ] ++ ; XY [ arr [ i ] ] ++ ; } int xAns = 0 , yAns = 0 , xyAns = 0 ; for ( auto xCoordinatePair : X ) { int xFrequency = xCoordinatePair . second ; int sameXPairs = ( xFrequency * ( xFrequency - 1 ) ) / 2 ; xAns += sameXPairs ; } for ( auto yCoordinatePair : Y ) { int yFrequency = yCoordinatePair . second ; int sameYPairs = ( yFrequency * ( yFrequency - 1 ) ) / 2 ; yAns += sameYPairs ; } for ( auto XYPair : XY ) { int xyFrequency = XYPair . second ; int samePointPairs = ( xyFrequency * ( xyFrequency - 1 ) ) / 2 ; xyAns += samePointPairs ; } return ( xAns + yAns - xyAns ) ; } int main ( ) { pair < int , int > arr [ ] = { { 1 , 2 } , { 2 , 3 } , { 1 , 3 } } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << findManhattanEuclidPair ( arr , n ) << endl ; return 0 ; }