Cuenta de paralelogramos en un plano

Dados algunos puntos en un plano, que son distintos y tres de ellos no se encuentran en la misma línea. Necesitamos encontrar el número de paralelogramos con los vértices como los puntos dados. Ejemplos:

Input : points[] = {(0, 0), (0, 2), (2, 2), (4, 2), 
                                   (1, 4), (3, 4)}
Output : 2
Two Parallelograms are possible by choosing above
given point as vertices, which are shown in below 
diagram.

Podemos resolver este problema usando una propiedad especial de los paralelogramos de que las diagonales de un paralelogramo se cortan entre sí en el medio. Entonces, si obtenemos un punto medio que es el punto medio de más de un segmento de línea, entonces podemos concluir que existe un paralelogramo, con mayor precisión si un punto medio ocurre x veces, entonces las diagonales de posibles paralelogramos se pueden elegir en ^x C ₂maneras, es decir, habrá x*(x-1)/2 paralelogramos correspondientes a este punto medio particular con una frecuencia x. Así que iteramos sobre todos los pares de puntos y calculamos su punto medio y aumentamos la frecuencia del punto medio en 1. Al final, contamos el número de paralelogramos según la frecuencia de cada punto medio distinto como se explicó anteriormente. Como solo necesitamos la frecuencia del punto medio, la división por 2 se ignora al calcular el punto medio por simplicidad. 

// C++ program to get number of Parallelograms we
// can make by given points of the plane
#include <bits/stdc++.h>
using namespace std;
 
// Returns count of Parallelograms possible
// from given points
int countOfParallelograms(int x[], int y[], int N)
{
    // Map to store frequency of mid points
    map<pair<int, int>, int> cnt;
    for (int i=0; i<N; i++)
    {
        for (int j=i+1; j<N; j++)
        {
            // division by 2 is ignored, to get
            // rid of doubles
            int midX = x[i] + x[j];
            int midY = y[i] + y[j];
 
            // increase the frequency of mid point
            cnt[make_pair(midX, midY)]++;
        }
    }
 
    // Iterating through all mid points
    int res = 0;
    for (auto it = cnt.begin(); it != cnt.end(); it++)
    {
        int freq = it->second;
 
        // Increase the count of Parallelograms by
        // applying function on frequency of mid point
        res += freq*(freq - 1)/2
    }
 
    return res;
}
 
// Driver code to test above methods
int main()
{
    int x[] = {0, 0, 2, 4, 1, 3};
    int y[] = {0, 2, 2, 2, 4, 4};
    int N = sizeof(x) / sizeof(int);
 
    cout << countOfParallelograms(x, y, N) << endl;
 
    return 0;
}

// JavaScript program to get number of Parallelograms we
// can make by given points of the plane
 
// Returns count of Parallelograms possible
// from given points
function countOfParallelograms(x, y, N)
{
    // Map to store frequency of mid points
    // map<pair<int, int>, int> cnt;
    let cnt = new Map();
    for (let i=0; i<N; i++)
    {
        for (let j=i+1; j<N; j++)
        {
            // division by 2 is ignored, to get
            // rid of doubles
            let midX = x[i] + x[j];
            let midY = y[i] + y[j];
 
            // increase the frequency of mid point
            let make_pair = [midX, midY];
            if(cnt.has(make_pair.join(''))){
                cnt.set(make_pair.join(''), cnt.get(make_pair.join('')) + 1);
            }
            else{
                cnt.set(make_pair.join(''), 1);
            }
        }
    }
 
    // Iterating through all mid points
    let res = 0;
    for (const [key, value] of cnt)
    {
        let freq = value;
        // Increase the count of Parallelograms by
        // applying function on frequency of mid point
        res = res + Math.floor(freq*(freq - 1)/2);
    }
 
    return res;
}
 
// Driver code to test above methods
let x = [0, 0, 2, 4, 1, 3];
let y = [0, 2, 2, 2, 4, 4];
let N = x.length;
 
console.log(countOfParallelograms(x, y, N));
 
// The code is contributed by Gautam goel (gautamgoel962)

Producción:

2

Complejidad de tiempo: O (n ² logn), ya que estamos iterando a través de dos bucles hasta n y también usamos un mapa que toma logn.
Espacio Auxiliar: O(n)

Este artículo es una contribución de Utkarsh Trivedi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.