ПРЕБРОЯВАНЕ НА УСПОРЕДНИЦИ В РАВНИНА

Дадени са точки на равнина, които са различни и нито една три от тях не лежат на една права. Трябва да намерим броя на успоредниците с върховете като дадените точки. Примери:

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 пъти, тогава диагоналите на възможните успоредници могат да бъдат избрани в ^хВ ₂начини, т.е. ще има 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.

    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)