题解：P9423 [蓝桥杯 2023 国 B] 数三角

· · 题解

因为 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;
}