| Time Limit: 2 second(s) | Memory Limit: 32 MB |
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 integersx 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 |
Output for 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 |
Case 1: 5 Case 2: 6 |
题解：
给一系列点，让找到可以组成的平行四边形的个数；
思路：由于平行四边形的交点是唯一的，那么我们只要记录每两个直线的交点，判断交点重复的个数可以求出来了；假设有这个交点有三个重复的，则ans+=3*2/2;
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
typedef long long LL;
const int MAXN=;
struct Dot{
double x,y;
bool operator < (const Dot &b) const{
if(x!=b.x)return x<b.x;
else return y<b.y;
}
};
Dot dt[MAXN];
Dot num[MAXN*MAXN];
int main(){
int T,N,kase=;
scanf("%d",&T);
while(T--){
scanf("%d",&N);
for(int i=;i<N;i++)scanf("%lf%lf",&dt[i].x,&dt[i].y);
int tp=;
for(int i=;i<N;i++)
for(int j=i+;j<N;j++){
if(dt[i].x==dt[j].x&&dt[i].y==dt[j].y)continue;
num[tp].y=(dt[i].y+dt[j].y)/;
num[tp].x=(dt[i].x+dt[j].x)/;
tp++;
}
sort(num,num+tp);
LL ans=,cur=;
for(int i=;i<tp;i++){
if(num[i].x==num[i-].x&&num[i].y==num[i-].y)cur++;
else{
ans+=cur*(cur-)/;cur=;
}
}
printf("Case %d: %lld\n",++kase,ans);
}
return ;
}