平面中平行四边形的计数-yiteyi-C++库

给定平面上的一些点，它们是不同的，并且没有三个位于同一条线上。我们需要找到以顶点为给定点的平行四边形的数目。例如：

null

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.

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

我们可以利用平行四边形对角线在中间相交的特殊性质来解决这个问题。所以如果我们得到这样一个中点，它是多条线段的中点，那么我们可以得出平行四边形存在的结论，更准确地说，如果一个中点出现x次，那么可以选择可能的平行四边形的对角线 ^十、 C _2. 方法，也就是说，有x*（x-1）/2个平行四边形对应于这个特定的中点，频率为x。所以我们迭代所有的点对，计算它们的中点，并将中点的频率增加1。最后，我们根据每个不同中点的频率计算平行四边形的数量，如上所述。由于我们只需要中间点的频率，为了简单起见，在计算中间点时忽略了除以2。

                     // C++ program to get number of Parallelograms we                   
                     // can make by given points of the plane                   
                     #include <bits/stdc++.h>                   
                     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;                   
                     }                   

输出：

本文由 乌特卡什·特里维迪 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用贡献极客。组织或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。

如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章