#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int,int>
#define endl '\n'
#define print(x) cout<<#x<<'='<<(x)<<endl;
int n;
const int N=3e3+5;
int x[N],y[N];
ll ans=0;
unordered_map<ll,ll> mp;
map<PII,int> vis;
ll dis(int i,int j)
{
return (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>x[i]>>y[i];
}
for(int i=1;i<=n;i++)
{
mp.clear();
vis.clear();
for(int j=1;j<=n;j++)
{
if(i==j)
{
continue;
}
vis[{x[j],y[j]}]=1;
mp[dis(i,j)]++;
//(a,b),(x[j],y[j])的中点坐标是(x[i],y[i])
int a=2*x[i]-x[j];
int b=2*y[i]-y[j];
if(mp[dis(i,j)]>=2)
{
if(vis[{a,b}]==1)//三点共线
{
ans+=mp[dis(i,j)]-1-1;
}
else
{
ans+=mp[dis(i,j)]-1;
}
}
}
}
cout<<ans;
}我觉得作者的数据是错的。我的代码可以在牛客上过掉69%(剩下的是因为超时,但是我感觉o(n^2)的应该可以呀),但是在本网站上就是WA。牛客上的原题:等腰三角形(hard) (nowcoder.com)
0 回复
0 转发
1 喜欢
7 阅读



