Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题意：给出n（n<=1E3）个不同的点，问最多组成多少个平行四边形。
思路：这道题的关键是，对于平行四边形的判断条件，要利用平行四边形对角线的交点平分两条对角线的性质。
也就是说，如果两条线段的对角线重合，那么一定可以组成一个平行四边形。
因此统计中点的位置即可，复杂度nnlg(n*n)
代码实现
1/* ***********************************************
2Author :111qqz
3Created Time :2016年11月22日 星期二 22时43分26秒
4File Name :code/poj/1971.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33struct point
34{
35 int x,y;
36 bool operator < (point b)const
37 {
38 if (x==b.x) return y<b.y;
39 return x<b.x;
40 }
41}p[1005],mid[1001*1001];
42int n;
43int main()
44{
45 #ifndef ONLINE_JUDGE
46 freopen("code/in.txt","r",stdin);
47 #endif
48 int T;
49 cin>>T;
50 while (T--)
51 {
52 ms(mp,0);
53 scanf("%d",&n);
54 for ( int i = 1; i <= n ; i++) scanf("%d%d",&p[i].x,&p[i].y);
55 int cnt = 0 ;
56 for ( int i = 1; i <= n ; i++)
57 for ( int j = i +1 ; j <= n ;j++)
58 {
59 mid[++cnt].x = p[i].x + p[j].x;
60 mid[cnt].y = p[i].y + p[j].y;
61 }
62
63 sort(mid+1,mid+cnt+1);
64 LL ans = 0 ;
65 int num = 0 ;
66 for ( int i = 1; i <= cnt-1 ; i++)
67 {
68 if (mid[i].x==mid[i+1].x&&mid[i].y==mid[i+1].y)
69 {
70 num++;
71 ans = ans + num;
72 }
73 else
74 {
75 num = 0 ;
76 }
77 }
78 printf("%lld\n",ans);
79 }
80
81
82 #ifndef ONLINE_JUDGE
83 fclose(stdin);
84 #endif
85 return 0;
86}