Gegeben sind einige Punkte auf einer Ebene, die unterschiedlich sind und von denen keine drei auf derselben Linie liegen. Wir müssen die Anzahl der Parallelogramme ermitteln, deren Eckpunkte die angegebenen Punkte sind. Beispiele:
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. Wir können dieses Problem lösen, indem wir eine spezielle Eigenschaft von Parallelogrammen nutzen, dass sich die Diagonalen eines Parallelogramms in der Mitte schneiden. Wenn wir also einen solchen Mittelpunkt erhalten, der der Mittelpunkt von mehr als einem Liniensegment ist, können wir schließen, dass ein Parallelogramm genauer existiert, wenn ein Mittelpunkt x-mal vorkommt, dann können Diagonalen möglicher Parallelogramme ausgewählt werdenXC2d. h. es wird x*(x-1)/2 Parallelogramme geben, die diesem bestimmten Mittelpunkt mit einer Frequenz x entsprechen. Also iterieren wir über alle Punktpaare, berechnen deren Mittelpunkt und erhöhen die Häufigkeit der Mittelpunkte um 1. Am Ende zählen wir die Anzahl der Parallelogramme entsprechend der Häufigkeit jedes einzelnen Mittelpunkts, wie oben erläutert. Da wir nur die Häufigkeit des Mittelpunkts benötigen, wird die Division durch 2 der Einfachheit halber bei der Berechnung des Mittelpunkts ignoriert.
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)
Ausgabe
2
Zeitkomplexität: An2logn), da wir zwei Schleifen bis zu n durchlaufen und auch eine Karte verwenden, die logn akzeptiert.
Hilfsraum: An)
Quiz erstellen