题目大意:给出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
8using namespace std;
9
10struct Node
11{
12 int x,y;
13}node[1010],mid[1001000];
14int T,n,summ,num;
15
16int 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
21int count(int k)
22{
23 if (k==1) return 0;
24 else
25 {
26 return k*(k-1)/2;
27 }
28}
29
30int 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