【CodeForces 660D】Number of Parallelograms

You are given n points on a plane. All the points are distinct and no three of them lie on the same line. Find the number of parallelograms with the vertices at the given points.

Input

The first line of the input contains integer n (1 ≤ n ≤ 2000) — the number of points.

Each of the next n lines contains two integers (x_i, y_i) (0 ≤ x_i, y_i ≤ 10⁹) — the coordinates of the i-th point.

Output

Print the only integer c — the number of parallelograms with the vertices at the given points.

4
0 1
1 0
1 1
2 0

1

給你n個點的坐標，問這n個點能形成多少個不相同的平行四邊形？

根據平行四邊形的性質，兩條對角線相交於一點，所以可以將這n個點兩兩連接並找出它們的中點並記錄下來。

然後根據這些中點來判斷有多少個平行四邊形，因為只要有兩個中點重合，那麼它們兩條線就可以組成一個平行四邊形。

所以先找出重合中點的個數s，那麼它們可以組成的平行四邊形個數為C(s,2)。

將它們求和即為所求。

#include<bits/stdc++.h>
using namespace std;
struct p
{
    int x,y;
}a[2001];
int com(int n,int m)
{
    int i,s=1;
    for(i=1;i<=m;i++)
    s=s*(n+1-i)/i;
    return s;
} 
int main()
{
    int n,i,j,k,s=0;
    map<pair<int,int>,int>ma;
    map<pair<int,int>,int>::iterator it;
    cin>>n;
    for(i=1;i<=n;i++)
        scanf("%d%d",&a[i].x,&a[i].y);
        
    for(i=1;i<=n-1;i++)
        for(j=i+1;j<=n;j++)
            ma[make_pair(a[i].x+a[j].x,a[i].y+a[j].y)]++;
            
    for(it=ma.begin();it!=ma.end();it++)
        s=s+com(it->second,2);
        
    printf("%d\n",s);
    return 0;
}