Dada una array arr que contiene N puntos, la tarea es encontrar el número total de tripletas en las que los puntos son equidistantes.
Se dice que un triplete de puntos (P1, P2, P3) es equidistante cuando la distancia entre P1 y P2 es igual a la distancia entre P1 y P3.
Nota: El orden de los puntos es importante, es decir, (P1, P2, P3) es diferente de (P2, P3, P1).
Ejemplo:
Entrada: arr = [[0, 0], [1, 0], [2, 0]]
Salida: 2
Explicación:
Dado que el orden de los puntos importa, tenemos dos conjuntos diferentes de puntos [[1, 0], [0, 0], [2, 0]] y [[1, 0], [2, 0], [0, 0]] en los que los puntos son equidistantes.Entrada: arr = [[1, 1], [1, 3], [2, 0]]
Salida: 0
Explicación:
No es posible obtener ningún triplete en el que los puntos sean equidistantes.
Planteamiento: Para resolver el problema mencionado anteriormente, sabemos que el orden de un triplete importa, por lo que podría haber más de una permutación del mismo triplete que satisfaga la condición de un par de puntos equidistantes.
- Primero, calcularemos todas las permutaciones de un triplete que tiene puntos equidistantes.
- Repita este mismo proceso para cada triplete diferente de puntos en la lista. Para calcular la distancia utilizaremos el cuadrado de la distancia entre las respectivas coordenadas .
- Use hashmap para almacenar varios números de pares de puntos equidistantes para un solo triplete.
- Tan pronto como contamos el número total de pares, calculamos la permutación requerida. Repetimos este proceso para todos los tripletes diferentes y agregamos todas las permutaciones a nuestro resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to Find
// the total number of Triplets
// in which the points are Equidistant
#include <bits/stdc++.h>
using namespace std;
// function to count such triplets
int numTrip(vector<pair<int, int> >& points)
{
int res = 0;
// Iterate over all the points
for (int i = 0; i < points.size(); ++i) {
unordered_map<long, int>
map(points.size());
// Iterate over all points other
// than the current point
for (int j = 0; j < points.size(); ++j) {
if (j == i)
continue;
int dy = points[i].second
- points[j].second;
int dx = points[i].first
- points[j].first;
// Compute squared euclidean distance
// for the current point
int key = dy * dy;
key += dx * dx;
map[key]++;
}
for (auto& p : map)
// Compute nP2 that is n * (n - 1)
res += p.second * (p.second - 1);
}
// Return the final result
return res;
}
// Driver code
int main()
{
vector<pair<int, int> > mat
= { { 0, 0 }, { 1, 0 }, { 2, 0 } };
cout << numTrip(mat);
return 0;
}
Java
// Java implementation to find the total
// number of Triplets in which the
// points are Equidistant
import java.util.*;
@SuppressWarnings("unchecked")
class GFG{
static class pair
{
public int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Function to size() such triplets
static int numTrip(ArrayList points)
{
int res = 0;
// Iterate over all the points
for(int i = 0; i < points.size(); ++i)
{
HashMap<Long,
Integer> map = new HashMap<>();
// Iterate over all points other
// than the current point
for(int j = 0; j < points.size(); ++j)
{
if (j == i)
continue;
int dy = ((pair)points.get(i)).second -
((pair)points.get(j)).second;
int dx = ((pair)points.get(i)).first -
((pair)points.get(j)).first;
// Compute squared euclidean distance
// for the current point
long key = dy * dy;
key += dx * dx;
if (map.containsKey(key))
{
map.put(key, map.get(key) + 1);
}
else
{
map.put(key, 1);
}
}
for(int p : map.values())
// Compute nP2 that is n * (n - 1)
res += p * (p - 1);
}
// Return the final result
return res;
}
// Driver code
public static void main(String []args)
{
ArrayList mat = new ArrayList();
mat.add(new pair(0, 0));
mat.add(new pair(1, 0));
mat.add(new pair(2, 0));
System.out.println(numTrip(mat));
}
}
// This code is contributed by rutvik_56
Python3
# Python3 implementation to find
# the total number of Triplets
# in which the points are Equidistant
# Function to count such triplets
def numTrip(points):
res = 0
# Iterate over all the points
for i in range(len(points)):
map = {}
# Iterate over all points other
# than the current point
for j in range(len(points)):
if (j == i):
continue
dy = points[i][1] - points[j][1]
dx = points[i][0] - points[j][0]
# Compute squared euclidean distance
# for the current point
key = dy * dy
key += dx * dx
map[key] = map.get(key, 0) + 1
for p in map:
# Compute nP2 that is n * (n - 1)
res += map[p] * (map[p] - 1)
# Return the final result
return res
# Driver code
if __name__ == '__main__':
mat = [ [ 0, 0 ],
[ 1, 0 ],
[ 2, 0 ] ]
print (numTrip(mat))
# This code is contributed by mohit kumar 29
C#
// C# implementation to find the total
// number of Triplets in which the
// points are Equidistant
using System;
using System.Collections;
using System.Collections.Generic;
class GFG{
class pair
{
public int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Function to count such triplets
static int numTrip(ArrayList points)
{
int res = 0;
// Iterate over all the points
for(int i = 0; i < points.Count; ++i)
{
Dictionary<long,
int> map = new Dictionary<long,
int>();
// Iterate over all points other
// than the current point
for(int j = 0; j < points.Count; ++j)
{
if (j == i)
continue;
int dy = ((pair)points[i]).second -
((pair)points[j]).second;
int dx = ((pair)points[i]).first -
((pair)points[j]).first;
// Compute squared euclidean distance
// for the current point
int key = dy * dy;
key += dx * dx;
if (map.ContainsKey(key))
{
map[key]++;
}
else
{
map[key] = 1;
}
}
foreach(int p in map.Values)
// Compute nP2 that is n * (n - 1)
res += p * (p - 1);
}
// Return the final result
return res;
}
// Driver code
public static void Main(string []args)
{
ArrayList mat = new ArrayList(){ new pair(0, 0),
new pair(1, 0),
new pair(2, 0) };
Console.Write(numTrip(mat));
}
}
// This code is contributed by pratham76
Javascript
<script>
// Javascript implementation to find the total
// number of Triplets in which the points are
// Equidistant
// Function to size() such triplets
function numTrip(points)
{
let res = 0;
// Iterate over all the points
for(let i = 0; i < points.length; ++i)
{
let map = new Map();
// Iterate over all points other
// than the current point
for(let j = 0; j < points.length; ++j)
{
if (j == i)
continue;
let dy = points[i][1] -
points[j][1];
let dx = points[i][0] -
points[j][0];
// Compute squared euclidean distance
// for the current point
let key = dy * dy;
key += dx * dx;
if (map.has(key))
{
map.set(key, map.get(key) + 1);
}
else
{
map.set(key, 1);
}
}
for(let [key, value] of map.entries())
// Compute nP2 that is n * (n - 1)
res += value * (value - 1);
}
// Return the final result
return res;
}
// Driver code
let mat = [];
mat.push([0, 0]);
mat.push([1, 0]);
mat.push([2, 0]);
document.write(numTrip(mat));
// This code is contributed by unknown2108
</script>
Producción:
2
Complejidad temporal: O(N 2 )
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por si_shubham y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA