En un plano cartesiano dado, hay N puntos. La tarea es encontrar el número de pares de puntos (A, B) tales que
- El punto A y el punto B no coinciden.
- La Distancia Manhattan y la Distancia Euclidiana entre los puntos deben ser iguales.
Nota: El par de 2 puntos (A, B) se considera igual que el par de 2 puntos (B, A).
Distancia Manhattan = |x2-x1|+|y2-y1|
Distancia Euclidiana = ((x2-x1)^2 + (y2-y1)^2)^0.5 donde los puntos son (x1, y1) y (x2, y2).
Ejemplos:
Entrada: N = 3, Puntos = {{1, 2}, {2, 3}, {1, 3}}
Salida: 2
Los pares son:
1) (1, 2) y (1, 3)
Distancia euclidiana de ( 1, 2) y (1, 3) = &root;((1 – 1) 2 + (3 – 2) 2 ) = 1
Distancia Manhattan de (1, 2) y (1, 3) = |(1 – 1 )| + |(2 – 3)| = 1
2) (1, 3) y (2, 3)
Distancia euclidiana de (1, 3) y (2, 3) = &root;((1 – 2) 2 + (3 – 3) 2 ) = 1
Manhattan distancia de (1, 3) y (2, 3) = |(1 – 2)| + |(3 – 3)| = 1
Entrada: N = 3, Puntos = { {1, 1}, {2, 3}, {1, 1} }
Salida: 0
Aquí ninguno de los pares cumple las dos condiciones anteriores
Enfoque: Al resolver la ecuación
|x2-x1|+|y2-y1| = sqrt((x2-x1)^2+(y2-y1)^2)
obtenemos, x2 = x1 o y2 = y1.
Considere 3 mapas,
1) Mapa X, donde X[x i ] almacena el número de puntos que tienen su coordenada x igual a x i
2) Mapa Y, donde Y[y i ] almacena el número de puntos que tienen su coordenada y igual a y i
3) Mapa XY, donde XY[(X i , Y i )] almacena el número de puntos coincidentes con el punto (x i , y i )
Ahora,
sea Xans el Número de pares con las mismas coordenadas X = X[x i ] 2 para todo x i distinto =
Sea Yans el Número de pares con las mismas coordenadas Y =Y[x i ] 2 para todos los y i
distintos Sea XYans el número de puntos coincidentes = XY[{x i , y i }] 2 para todos los puntos distintos (x i , y i )
Por lo tanto, la respuesta requerida = Xans + Yans – XYans
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the number of non coincident
// pairs of points with manhattan distance
// equal to euclidean distance
int findManhattanEuclidPair(pair<int, int> arr[], int n)
{
// To store frequency of all distinct Xi
map<int, int> X;
// To store Frequency of all distinct Yi
map<int, int> Y;
// To store Frequency of all distinct
// points (Xi, Yi);
map<pair<int, int>, int> XY;
for (int i = 0; i < n; i++) {
int xi = arr[i].first;
int yi = arr[i].second;
// Hash xi coordinate
X[xi]++;
// Hash yi coordinate
Y[yi]++;
// Hash the point (xi, yi)
XY[arr[i]]++;
}
int xAns = 0, yAns = 0, xyAns = 0;
// find pairs with same Xi
for (auto xCoordinatePair : X) {
int xFrequency = xCoordinatePair.second;
// calculate ((xFrequency) C2)
int sameXPairs
= (xFrequency * (xFrequency - 1)) / 2;
xAns += sameXPairs;
}
// find pairs with same Yi
for (auto yCoordinatePair : Y) {
int yFrequency = yCoordinatePair.second;
// calculate ((yFrequency) C2)
int sameYPairs
= (yFrequency * (yFrequency - 1)) / 2;
yAns += sameYPairs;
}
// find pairs with same (Xi, Yi)
for (auto XYPair : XY) {
int xyFrequency = XYPair.second;
// calculate ((xyFrequency) C2)
int samePointPairs
= (xyFrequency * (xyFrequency - 1)) / 2;
xyAns += samePointPairs;
}
return (xAns + yAns - (2 * xyAns));
/* we are subtracting 2 * xyAns because we have counted
let say A,B coinciding points two times in xAns and
yAns which should not be add to the final answer so
we are subtracting xyAns 2 times. */
}
// Driver Code
int main()
{
pair<int, int> arr[]
= { { 1, 2 }, { 1, 2 }, { 4, 3 }, { 1, 3 } };
int n = sizeof(arr) / sizeof(arr[0]);
cout << findManhattanEuclidPair(arr, n) << endl;
return 0;
}
Python3
# Python3 implementation of the # above approach from collections import defaultdict # Function to return the number of # non coincident pairs of points with # manhattan distance equal to # euclidean distance def findManhattanEuclidPair(arr, n): # To store frequency of all distinct Xi X = defaultdict(lambda:0) # To store Frequency of all distinct Yi Y = defaultdict(lambda:0) # To store Frequency of all distinct # points (Xi, Yi) XY = defaultdict(lambda:0) for i in range(0, n): xi = arr[i][0] yi = arr[i][1] # Hash xi coordinate X[xi] += 1 # Hash yi coordinate Y[yi] += 1 # Hash the point (xi, yi) XY[tuple(arr[i])] += 1 xAns, yAns, xyAns = 0, 0, 0 # find pairs with same Xi for xCoordinatePair in X: xFrequency = X[xCoordinatePair] # calculate ((xFrequency) C2) sameXPairs = (xFrequency * (xFrequency - 1)) // 2 xAns += sameXPairs # find pairs with same Yi for yCoordinatePair in Y: yFrequency = Y[yCoordinatePair] # calculate ((yFrequency) C2) sameYPairs = (yFrequency * (yFrequency - 1)) // 2 yAns += sameYPairs # find pairs with same (Xi, Yi) for XYPair in XY: xyFrequency = XY[XYPair] # calculate ((xyFrequency) C2) samePointPairs = (xyFrequency * (xyFrequency - 1)) // 2 xyAns += samePointPairs return (xAns + yAns - 2 * xyAns) # we are subtracting 2 * xyAns because we have counted let say A,B coinciding points two times # in xAns and yAns which should not be add to the final answer so we are subtracting xyAns 2 times. # Driver Code if __name__ == "__main__": arr = [[1, 2], [1,2], [4, 3], [1, 3]] n = len(arr) print(findManhattanEuclidPair(arr, n)) # This code is contributed by Rituraj Jain
3
Complejidad de tiempo : O(NlogN), donde N es el número de puntos
Complejidad de espacio : O(N), ya que se ha tomado N espacio adicional.