A paralelogrammák száma egy síkban
Adott néhány pont egy síkon, amelyek különböznek egymástól, és nincs három ugyanazon az egyenesen. Meg kell találnunk a párhuzamok számát, amelyek csúcsai a megadott pontok. Példák:
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. Ezt a feladatot úgy tudjuk megoldani, hogy a paralelogrammák azon speciális tulajdonságát használjuk, hogy a paralelogramma átlói középen metszik egymást. Tehát ha egy olyan középpontot kapunk, amely egynél több szakasz középpontja, akkor azt a következtetést vonhatjuk le, hogy a paralelogramma pontosabban létezik, ha egy középpont x-szer fordul elő, akkor a lehetséges paralelogrammák átlói kiválaszthatók. x C 2 azaz x*(x-1)/2 paralelogramma lesz ennek a bizonyos középpontnak megfelelő x gyakorisággal. Tehát iterálunk minden pontpáron, és kiszámítjuk a középpontjukat, és növeljük a középpont gyakoriságát 1-gyel. A végén megszámoljuk a paralelogrammákat az egyes középpontok gyakorisága szerint, a fentebb leírtak szerint. Mivel csak a középpont 2-vel való osztásának gyakoriságára van szükség, figyelmen kívül hagyjuk a középpont kiszámításakor az egyszerűség kedvéért.
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)
Kimenet
2
Időbeli összetettség: On 2 logn), mivel két cikluson keresztül iterálunk n-ig, és egy térképet is használunk, amely logn-t vesz fel.
Kiegészítő tér: On)
Kvíz létrehozása
