题目大意:给出n个点,求出这n个点能够组成平行四边形的个数。
解题思路:1)平行四边形的对角线的中点一定相交。<=> 如果有两条不同线段的中点相交,就是一个平行四边形
2)利用点坐标求出中点的集合,离散化后求出同个中点的出现的个数k。
3)对于每一个k ,利用组合公式C(k,2)的答案就是平行四边行的个数
代码:
1
#include <iostream>
2
#include <cstdio>
3
#include <cmath>
4
#include <cstring>
5
#include <string>
6
#include <algorithm>
7
8
using namespace std;
9
10
struct Node
11

{
12
int x,y;
13
}node[1010],mid[1001000];
14
int T,n,summ,num;
15
16
int cmp(const Node &a,const Node &b)
17

{
18
if (a.x==b.x) return a.y<b.y; else return a.x<b.x;
19
}
20
21
int count(int k)
22

{
23
if (k==1) return 0;
24
else
25
{
26
return k*(k-1)/2;
27
}
28
}
29
30
int main()
31

{
32
cin >> T;
33
while (T--)
34
{
35
summ=0;
36
scanf("%d",&n);
37
for (int i=1; i<=n; i++)
38
{
39
scanf("%d%d",&(node[i].x),&(node[i].y));
40
}
41
num=-1;
42
for (int i=1; i<=n; i++)
43
{
44
for (int j=i+1; j<=n; j++)
45
{
46
num++;
47
mid[num].x=node[i].x+node[j].x;
48
mid[num].y=node[i].y+node[j].y;
49
}
50
}
51
sort(mid,mid+num+1,cmp);
52
Node temp;
53
int k;
54
k=1;
55
for (int i=0; i<=num; i++)
56
{
57
if (mid[i].x==mid[i+1].x && mid[i].y==mid[i+1].y) k++;
58
else
59
{
60
summ+=count(k);
61
k=1;
62
}
63
}
64
cout << summ << endl;
65
66
}
67
return 0;
68
}
69