Dados alguns pontos em um plano que são distintos e não há três deles na mesma linha. Precisamos encontrar o número de paralelogramos com os vértices como pontos dados. Exemplos:
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 utilizando uma propriedade especial dos paralelogramos: as diagonais de um paralelogramo intersectam-se no meio. Portanto, se obtivermos um ponto médio que é o ponto médio de mais de um segmento de linha, podemos concluir que um paralelogramo existe com mais precisão se um ponto médio ocorrer x vezes, então as diagonais de paralelogramos possíveis podem ser escolhidas emxC2maneiras, ou seja, haverá x*(x-1)/2 paralelogramos correspondentes a este ponto médio específico com uma frequência x. Então, iteramos sobre todos os pares de pontos e calculamos seu ponto médio e aumentamos a frequência do ponto médio em 1. No final, contamos o número de paralelogramos de acordo com a frequência de cada ponto médio distinto, conforme explicado acima. Como precisamos apenas da frequência do ponto médio, a divisão por 2 é ignorada ao calcular o ponto médio para simplificar.
CPP// C++ program to get number of Parallelograms we // can make by given points of the plane #include
/*package whatever //do not write package name here */ import java.io.*; import java.util.*; public class GFG { // Returns count of Parallelograms possible // from given points public static int countOfParallelograms(int[] x int[] y int N) { // Map to store frequency of mid points HashMap<String Integer> cnt = new HashMap<>(); 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 String temp = String.join(' ' String.valueOf(midX) String.valueOf(midY)); if(cnt.containsKey(temp)){ cnt.put(temp cnt.get(temp) + 1); } else{ cnt.put(temp 1); } } } // Iterating through all mid points int res = 0; for (Map.Entry<String Integer> it : cnt.entrySet()) { int freq = it.getValue(); // Increase the count of Parallelograms by // applying function on frequency of mid point res = res + freq*(freq - 1)/2; } return res; } public static void main(String[] args) { int[] x = {0 0 2 4 1 3}; int[] y = {0 2 2 2 4 4}; int N = x.length; System.out.println(countOfParallelograms(x y N)); } } // The code is contributed by Nidhi goel.
# python program to get number of Parallelograms we # can make by given points of the plane # Returns count of Parallelograms possible # from given points def countOfParallelograms(x y N): # Map to store frequency of mid points cnt = {} for i in range(N): for j in range(i+1 N): # division by 2 is ignored to get # rid of doubles midX = x[i] + x[j]; midY = y[i] + y[j]; # increase the frequency of mid point if ((midX midY) in cnt): cnt[(midX midY)] += 1 else: cnt[(midX midY)] = 1 # Iterating through all mid points res = 0 for key in cnt: freq = cnt[key] # 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 x = [0 0 2 4 1 3] y = [0 2 2 2 4 4] N = len(x); print(int(countOfParallelograms(x y N))) # The code is contributed by Gautam goel.
using System; using System.Collections.Generic; public class GFG { // Returns count of Parallelograms possible // from given points public static int CountOfParallelograms(int[] x int[] y int N) { // Map to store frequency of mid points Dictionary<string int> cnt = new Dictionary<string int>(); 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 string temp = string.Join(' ' midX.ToString() midY.ToString()); if (cnt.ContainsKey(temp)) { cnt[temp]++; } else { cnt.Add(temp 1); } } } // Iterating through all mid points int res = 0; foreach (KeyValuePair<string int> it in cnt) { int freq = it.Value; // Increase the count of Parallelograms by // applying function on frequency of mid point res += freq * (freq - 1) / 2; } return res; } public static void Main(string[] args) { int[] x = { 0 0 2 4 1 3 }; int[] y = { 0 2 2 2 4 4 }; int N = x.Length; Console.WriteLine(CountOfParallelograms(x y N)); } }
// 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 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)
Saída
2
Complexidade de tempo: Sobre2logn), pois estamos iterando através de dois loops até n e usando também um mapa que leva logn.
Espaço Auxiliar: Sobre)
Criar questionário