当前位置： 移动技术网 > IT编程>开发语言>C/C++ > 【CodeForces 660D】Number of Parallelograms

【CodeForces 660D】Number of Parallelograms

2018年04月15日  | 移动技术网IT编程  | 我要评论

无锡汽车票查询,醉回七九当农民txt,康熙来了20130521

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 (xi, yi) (0 ≤ xi, yi ≤ 109) — the coordinates of the i-th point.

Output

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

Sample Input
4
0 1
1 0
1 1
2 0
Output
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;
}

 



您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网