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, contains2 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
题目链接：http://lightoj.com/volume_showproblem.php?problem=1058
*******************************************************
题意：给出T组实例，每组实例给出n各个点的坐标，判断能后成多少个平行四边形。
分析：使用向量法判断，只要满足x1+x3=x2+x4,y1+y3=y2+y4，则说明可以构成平行四边行
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <cmath> 6 #include <stack> 7 #include <map> 8 #include <vector> 9 using namespace std; 10 11 #define N 1200 12 13 struct node 14 { 15 int x,y; 16 }p[N]; 17 18 node q[500000]; 19 20 bool cmp(node a,node b) 21 { 22 if(a.x==b.x) 23 return a.y<b.y; 24 return a.x<b.x; 25 } 26 27 int main() 28 { 29 int T ,kk=1,i,j,n; 30 31 scanf("%d", &T); 32 33 while(T--) 34 { 35 scanf("%d", &n); 36 37 for(i=0;i<n;i++) 38 scanf("%d%d", &p[i].x,&p[i].y); 39 40 int u=0; 41 for(i=0;i<n-1;i++)///保存好向量判断要用到的值 42 { 43 for(j=i+1;j<n;j++) 44 { 45 q[u].x=p[i].x+p[j].x; 46 q[u++].y=p[i].y+p[j].y; 47 } 48 } 49 50 sort(q,q+u,cmp); 51 52 int ans=0,f=0,sum=1; 53 for(i=1;i<u;i++)///使用向量法判定是否满足为平行四边形 54 { 55 if(q[i].x==q[f].x&&q[i].y==q[f].y) 56 sum++; 57 else 58 { 59 f=i;/// 60 ans+=sum*(sum-1)/2;///可以构成平行四边形的数目 61 sum=1; 62 } 63 } 64 65 printf("Case %d: %d\n",kk++,ans); 66 } 67 return 0; 68 }
附上一个RE的代码：（使用的斜率和b值判断的）指出一些错误和注意事项
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <cmath> 6 #include <stack> 7 #include <map> 8 #include <vector> 9 using namespace std; 10 11 #define N 12000 12 #define INF 0x3f3f3f3f 13 14 struct node 15 { 16 int x,y; 17 }p[N]; 18 19 struct no 20 { 21 double k,l,b; 22 }q[N];///应为q[500000]，对于储存统计比较条件的这个数组一定要开的更大，依旧为N的话RE无止境。。。 23 24 double Len(node a,node b) 25 { 26 double x=b.x-a.x; 27 double y=b.y-a.y; 28 double len=sqrt(x*x+y*y); 29 return len; 30 } 31 32 int main() 33 { 34 int T ,kk=1,i,j,n; 35 36 scanf("%d", &T); 37 38 while(T--) 39 { 40 scanf("%d", &n); 41 42 memset(p,0,sizeof(p)); 43 memset(q,0,sizeof(q)); 44 45 for(i=0;i<n;i++) 46 scanf("%d%d", &p[i].x,&p[i].y); 47 48 int u=0; 49 for(i=0;i<n-1;i++) 50 { 51 for(j=i+1;j<n;j++) 52 { 53 if(p[j].x-p[i].x!=0) 54 { 55 q[u].k=1.0*(p[j].y-p[i].y)/(p[j].x-p[i].x); 56 q[u].b=p[i].y-q[u].k*p[i].x; 57 q[u++].l=Len(p[i],p[j]); 58 } 59 else 60 { 61 q[u].k=INF; 62 q[u].b=p[i].x; 63 q[u++].l=Len(p[i],p[j]); 64 } 65 } 66 } 67 68 int ans=0; 69 for(i=0;i<u-1;i++)///上面的N改了之后就知道这双重for提交，TLE妥妥的，所以这里思路必须得换一下 70 { 71 for(j=i+1;j<u;j++)///然后我就直接改方法了，也不知道这个路子能被改出正确答案不%>_<% 72 { 73 if((q[i].k==q[j].k)&&(q[i].l==q[j].l)&&q[i].b != q[j].b) 74 ans++; 75 } 76 } 77 78 printf("Case %d: %d\n",kk++,ans/2);///这里显然也天真了 79 } 80 return 0; 81 }