POJ 1972 Parallelogram Counting

r囧r小猫 2022-08-27 15:55 141阅读 0赞

Parallelogram Counting

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;5000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;5799</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;1955</td> 
  </tr> 
 </tbody> 
</table>

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

The first line of the input contains a single integer t (1 <= t <= 10), the number of test cases. It is followed by the input data for each test case.  
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

Output should contain t lines.  
Line i contains an integer showing the number of the parallelograms as described above for test case i.

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

5
    6

Source

[Tehran Sharif 2004 Preliminary][]

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    struct node{
    	int x;
    	int y;
    }a[1100];
    
    struct node1//定义中点hash表。//平行四边形的性质，对角线交点为两对角线中点。所以两条线段中点重合就能构成平行四边形。
    {
    	int x;
    	int y;
    }zd[1100000];//事实证明用qsort 对int类型排序时间 优于 double类型排序；
    
    int cmp(const void *a,const void *b)
    {
         struct node *aa=(node *)a;
         struct node *bb=(node *)b;
    	 if((aa->x)!=(bb->x))
    		 return((aa->x)-(bb->x));
    	 else
    		 return((aa->y)-(bb->y));
    }
    
    int main()
    {
    	int t, n;
    	int i, j, k;
    	int m, sum;
    
    	scanf("%d", &t);
    	while(t--)
    	{
    		scanf("%d", &n);
    		for(i=0; i<n; i++)
    			scanf("%d%d", &a[i].x, &a[i].y);
    
    		k = 0;
    		for(i=0; i<n; i++)
    		{
    			for(j=i+1; j<n; j++)
    			{
    				zd[k].x = a[i].x + a[j].x;
    				zd[k].y = a[i].y + a[j].y;//之所以不直接存中点坐标是因为排序时间问题。
    				k++;
    			}
    		}
    		qsort(zd, k, sizeof(zd[0]), cmp);
    
    		m = 1;
    		sum = 0;
    		for(i=1; i<k; i++)
    		{
    			if((zd[i].x==zd[i-1].x) && (zd[i].y==zd[i-1].y))//统计同一中点的线段共有m条，所以能构成m*(m-1)/2个平行四边形。
    				m++;
    			else
    			{
    				m = m*(m-1)/2;
    				sum += m;
    				m = 1;
    			}
    		}
    		printf("%d\n", sum);
    	}
    
    	return 0;
    }

[Tehran Sharif 2004 Preliminary]: http://poj.org/searchproblem?field=source&key=Tehran+Sharif+2004+Preliminary