Nombre de parallélogrammes dans un plan
Étant donné certains points sur un plan qui sont distincts et qu'il n'y en a pas trois qui se trouvent sur la même ligne. Nous devons trouver le nombre de parallélogrammes avec les sommets comme points donnés. Exemples :
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. Nous pouvons résoudre ce problème en utilisant une propriété spéciale des parallélogrammes selon laquelle les diagonales d’un parallélogramme se coupent au milieu. Donc, si nous obtenons un tel point médian qui est le point médian de plus d'un segment de droite, alors nous pouvons conclure qu'un parallélogramme existe avec plus de précision si un point médian apparaît x fois, alors les diagonales des parallélogrammes possibles peuvent être choisies dans x C 2 de différentes manières, c'est-à-dire qu'il y aura x*(x-1)/2 parallélogrammes correspondant à ce point médian particulier avec une fréquence x. Nous parcourons donc toutes les paires de points, calculons leur point médian et augmentons la fréquence du point médian de 1. À la fin, nous comptons le nombre de parallélogrammes en fonction de la fréquence de chaque point médian distinct, comme expliqué ci-dessus. Comme nous avons juste besoin de la fréquence du point médian, la division par 2 est ignorée lors du calcul du point médian pour plus de simplicité.
CPP // C++ program to get number of Parallelograms we // can make by given points of the plane #include 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 ; }
Java /*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.
Python3 # 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.
C# 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 // 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)
Sortir
2
Complexité temporelle : Sur 2 logn) car nous parcourons deux boucles jusqu'à n et utilisons également une carte qui prend logn.
Espace auxiliaire : Sur)
Créer un quiz
