عدد متوازيات الأضلاع في المستوى

إذا كانت هناك بعض النقاط على المستوى المتميزة ولا تقع ثلاث منها على نفس الخط. نحن بحاجة إلى إيجاد عدد متوازيات الأضلاع التي تكون رؤوسها نقاطًا معينة. أمثلة:

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. 

يمكننا حل هذه المشكلة باستخدام خاصية خاصة لمتوازيات الأضلاع، وهي أن أقطار متوازي الأضلاع تتقاطع مع بعضها البعض في المنتصف. لذا، إذا حصلنا على هذه النقطة الوسطى وهي النقطة الوسطى لأكثر من قطعة مستقيمة، فيمكننا أن نستنتج أن متوازي الأضلاع موجود بشكل أكثر دقة إذا حدثت النقطة الوسطى x مرات، فيمكن اختيار أقطار متوازيات الأضلاع المحتملة في س ج 2 أي أنه سيكون هناك x*(x-1)/2 متوازي أضلاع يتوافق مع هذه النقطة الوسطى المحددة بتردد x. لذلك نقوم بالتكرار على كل زوج من النقاط ونحسب النقطة الوسطى الخاصة بهم ونزيد تردد النقطة الوسطى بمقدار 1. وفي النهاية نحسب عدد متوازيات الأضلاع وفقًا لتكرار كل نقطة وسطى مميزة كما هو موضح أعلاه. نظرًا لأننا نحتاج فقط إلى تجاهل تكرار تقسيم النقطة الوسطى على 2 أثناء حساب النقطة الوسطى من أجل البساطة. 

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)   

الإخراج
2 

تعقيد الوقت: على 2 logn) حيث أننا نقوم بالتكرار من خلال حلقتين تصل إلى n ونستخدم الخريطة أيضًا والتي تأخذ تسجيل الدخول.
المساحة المساعدة: على)

إنشاء اختبار