CodeForces - 660D：Number of Parallelograms （问N个点多少个平行四边形）

佚名 6年前 (2019-04-14) 随笔 1300人围观抢沙发百度已收录

pro：给定N个点，问多少个点组成了平行四边形。保证没有三点共线。

sol：由于没有三点贡献，所以我们枚举对角线，对角线的中点重合的就是平行四边形。如果没说保证三点不共线就不能这么做，因为有可能4个点在一条直线上。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
map<pair<int,int>,int>mp;
int x[1010],y[1010];
int main()
{
    int N,ans=0;
    scanf("%d",&N);
    rep(i,1,N) scanf("%d%d",&x[i],&y[i]);
    rep(i,1,N)
     rep(j,i+1,N) {
         ans+=mp[make_pair(x[i]+x[j],y[i]+y[j])];
         mp[make_pair(x[i]+x[j],y[i]+y[j])]++;
    }
    printf("%d\n",ans);
    return 0;
}