Description
There are n distinct points in the plane, given by their integer coordinates. Find the number of parallelograms whose vertices lie on these points. In other words, find the number of 4-element subsets of these points that can be written as {A, B, C, D} such that AB || CD, and BC || AD. No four points are in a straight line.
Input
Input starts with an integer T (≤ 15), denoting the number of test cases.
The first line of each test case contains an integer n (1 ≤ n ≤ 1000). Each of the next n lines, contains 2 space-separated integers x and y (the coordinates of a point) with magnitude (absolute value) of no more than 1000000000.
Output
For each case, print the case number and the number of parallelograms that can be formed.
Sample Input
2
6
0 0
2 0
4 0
1 1
3 1
5 1
7
-2 -1
8 9
5 7
1 1
4 8
2 0
9 8
Sample Output
Case 1: 5
Case 2: 6
给出若干个点的坐标，问最多能构成平行四边形的个数.
思路：
如果两条直线的中点相同，那么着四个点就能构成平行四边形.
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; struct node{ int x,y; }arr[1010]; struct midd{ int midx,midy; }mid[500500]; bool cmp(midd a,midd b) { if(a.midx==b.midx) return a.midy<b.midy; else return a.midx<b.midx; } int main() { int t; scanf("%d",&t); int q=0; while(t--) { int n,i,j,l=0; scanf("%d",&n); for(i=0;i<n;i++) scanf("%d%d",&arr[i].x,&arr[i].y); for(i=0;i<n;i++) for(j=i+1;j<n;j++){ mid[l].midx=arr[i].x+arr[j].x; mid[l].midy=arr[i].y+arr[j].y; l++; } sort(mid,mid+l,cmp); int k=1; int st=0,ans=0; for(i=1;i<l;i++) { if(mid[i].midx==mid[st].midx&&mid[i].midy==mid[st].midy) k++; else { ans+=(k-1)*k/2;//C(n,2)的公式 k=1; st=i; } } printf("Case %d: ",++q); printf("%d\n",ans); } }