Pairs with same Manhattan and Euclidean distance | Python3 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
from collections import defaultdict NEW_LINE def findManhattanEuclidPair ( arr , n ) : NEW_LINE INDENT X = defaultdict ( lambda : 0 ) NEW_LINE Y = defaultdict ( lambda : 0 ) NEW_LINE XY = defaultdict ( lambda : 0 ) NEW_LINE for i in range ( 0 , n ) : NEW_LINE INDENT xi = arr [ i ] [ 0 ] NEW_LINE yi = arr [ i ] [ 1 ] NEW_LINE X [ xi ] += 1 NEW_LINE Y [ yi ] += 1 NEW_LINE XY [ tuple ( arr [ i ] ) ] += 1 NEW_LINE DEDENT xAns , yAns , xyAns = 0 , 0 , 0 NEW_LINE for xCoordinatePair in X : NEW_LINE INDENT xFrequency = X [ xCoordinatePair ] NEW_LINE sameXPairs = ( xFrequency * ( xFrequency - 1 ) ) // 2 NEW_LINE xAns += sameXPairs NEW_LINE DEDENT for yCoordinatePair in Y : NEW_LINE INDENT yFrequency = Y [ yCoordinatePair ] NEW_LINE sameYPairs = ( yFrequency * ( yFrequency - 1 ) ) // 2 NEW_LINE yAns += sameYPairs NEW_LINE DEDENT for XYPair in XY : NEW_LINE INDENT xyFrequency = XY [ XYPair ] NEW_LINE samePointPairs = ( xyFrequency * ( xyFrequency - 1 ) ) // 2 NEW_LINE xyAns += samePointPairs NEW_LINE DEDENT return ( xAns + yAns - xyAns ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ [ 1 , 2 ] , [ 2 , 3 ] , [ 1 , 3 ] ] NEW_LINE n = len ( arr ) NEW_LINE print ( findManhattanEuclidPair ( arr , n ) ) NEW_LINE DEDENT