2016福州大学第十三届程序设计竞赛 Problem C 平行四边形数（思维）

Problem C 平行四边形数

Accept: 82    Submit: 425 Time Limit: 2000 mSec    Memory Limit : 32768 KB

 Problem Description

在一个平面内给定n个点，任意三个点不在同一条直线上，用这些点可以构成多少个平行四边形？一个点可以同时属于多个平行四边形。

 Input

多组数据（<=10），处理到EOF。

每组数据第一行一个整数n(4<=n<=500)。接下来n行每行两个整数xi,yi(0<=xi,yi<=1e9)，表示每个点的坐标。

 Output

每组数据输出一个整数，表示用这些点能构成多少个平行四边形。

 Sample Input

40 11 01 12 0

 Sample Output

1

 Source

2016福州大学第十三届程序设计竞赛

平行四边形对角线互相平分，我们可以利用这一性质，判断每两个点连线的中点，是否有重合。

例：

AB,CD,EF中点相同，我们便可以从中选出3个平行四边形,即组合数C (3,2)。

#include<stdio.h> #include<algorithm> using namespace std; const int N = 500 + 10 ; struct xx { double x,y; } f[N],ff[N*N]; int cmp(xx a,xx b) { if(a.x==b.x) return a.y<b.y; return a.x<b.x; } int cal(int m) { return m*(m-1)/2; } int main() { int n; while(scanf("%d",&n)==1) { for(int i=0; i<n; i++) { scanf("%lf%lf",&f[i].x,&f[i].y); } int x=0; for(int i=0; i<n; i++) { for(int j=i+1; j<n; j++) { ff[x].x=(f[i].x+f[j].x)/2.0; ff[x].y=(f[i].y+f[j].y)/2.0; x++; } } sort(ff,ff+x,cmp); int sum=1,ans=0; for(int i=1; i<x; i++) { if(ff[i].x==ff[i-1].x&&ff[i].y==ff[i-1].y) sum++; else { ans+=cal(sum); sum=1; } if(i==x-1) { ans+=cal(sum); sum=1; } } printf("%d\n",ans); } }