自动搬运

查看原文

来自洛谷，原作者为

	s4CRIF1CbUbbL3AtIAly 僕だって空を飛べる / 雲になっていく / 風になっていく / いつかはみんな / 星になっていく

搬运于2025-08-24 22:48:14，当前版本为作者最后更新于2024-05-21 14:43:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

因为 $n$ 只有 $2\times 10^3$，所以可以先枚举每一个点作为顶点然后把其余所有点到顶点的距离都加入一个 map 当中，在加入过程中就可以计算出答案。

但是注意三点共线的情况，此时中间的那个点一定是两边两个点的中点才会被计入。

#include<bits/stdc++.h>
using namespace std;
long long x[2005],y[2005];
int n;
long long dis(int i,int j){return ((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));}
map<long long,int> cnt;
map<long long,map<long long,int> > mp;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>x[i]>>y[i],mp[x[i]][y[i]]=1;
    int ans=0;
    for(int i=1;i<=n;i++){
        cnt.clear();
        for(int j=1;j<=n;j++) ans+=cnt[dis(i,j)],cnt[dis(i,j)]++;// i,j 会与已有的哪些点构成等腰三角形
        for(int j=1;j<i;j++) if(((x[i]+x[j])%2==0)&&(y[i]+y[j])%2==0) ans-=mp[(x[i]+x[j])/2][(y[i]+y[j])/2];
    }
    cout<<ans<<endl;
    return 0;
}