Date su neke točke na ravnini koje su različite i nijedna od njih ne leži na istoj liniji. Trebamo pronaći broj paralelograma čiji su vrhovi dane točke. Primjeri:
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. Ovaj problem možemo riješiti korištenjem posebnog svojstva paralelograma da se dijagonale paralelograma sijeku u sredini. Dakle, ako dobijemo takvu središnju točku koja je središnja točka više od jednog segmenta linije, tada možemo zaključiti da paralelogram postoji točnije ako se središnja točka pojavljuje x puta, tada se dijagonale mogućih paralelograma mogu izabrati uxC2bit će x*(x-1)/2 paralelograma koji odgovaraju ovoj srednjoj točki s frekvencijom x. Dakle, ponavljamo sve parove točaka i izračunavamo njihovu srednju točku i povećavamo učestalost srednje točke za 1. Na kraju brojimo broj paralelograma prema učestalosti svake različite srednje točke kao što je gore objašnjeno. Kako nam samo treba učestalost dijeljenja srednje točke s 2 zanemaruje se pri izračunavanju srednje točke radi jednostavnosti.
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)
Izlaz
2
Vremenska složenost: Na2logn) jer ponavljamo kroz dvije petlje do n i također koristimo mapu koja uzima logn.
Pomoćni prostor: Na)
Napravi kviz