NC15321. 回旋星空
描述
曾经有两个来自吉尔尼斯的人(A和C)恋爱了,他们晚上经常在一起看头上的那片名为假的回旋星空,
有一天他们分手了,A想通过回旋星空测量他们之间的复合指数,测量的规则是,
计算回旋图标的个数,即选中三颗星星,分别作为回旋图标的起点,拐点和终点,假设现在有三个
星星分别为i,j,k,如果d(a[i],a[j]) == d(a[j],a[k])则表示找到了一个回旋图标,其中d(x,y)表示这两个点的欧氏距离
为了给它很大的希望(i,j,k)和(k,j,i)被认为是两个不同的回旋图标
A花了一晚上终于把整片星空映射到了一张二平面图上,由于星星太多以至于A有点懵逼,所以
输入描述
第一行一个整数T(T<=10),表示组数
对于每组数据有一个n,表示有n个小星星(0< n < 1000)
接下来跟着n行,每行跟两个整数xi和yi表示每个星星的坐标(-10000< xi, yi<10000)
输出描述
对于每组数据,如果没有找到回旋图标输出”WA”,否则输出找到图标个数
示例1
输入:
2 2 1 0 0 1 3 1 0 0 1 0 0
输出:
WA 2
C++14(g++5.4) 解法, 执行用时: 382ms, 内存消耗: 476K, 提交时间: 2019-09-03 15:22:31
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int const N = 1000 + 10;
map<int,int>mp;
int x[N],y[N];
int main(){
int T;
cin>>T;
while(T--){
int n; cin>>n;
for(int i=1;i<=n;i++)
scanf("%d%d",&x[i],&y[i]);
ll ans = 0;
for(int i=1;i<=n;i++){
mp.clear();
for(int j=1;j<=n;j++){
if(i == j) continue;
int dis = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);
mp[dis]++;
}
for(auto &k:mp){
ans += (k.second) * (k.second - 1) / 2;
}
}
if(ans == 0) printf("WA\n");
else printf("%lld\n",ans * 2);
}
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 541ms, 内存消耗: 476K, 提交时间: 2018-03-26 21:14:54
#include<bits/stdc++.h>
using namespace std;
int x[2000],y[2000];
map<int,int> p;
int main(){
int T,N;
cin>>T;
while(T--){
cin>>N;
for(int i=0;i<N;++i){
cin>>x[i]>>y[i];
}
int ans=0;
for(int i=0;i<N;++i){
p.clear();
for(int j=0;j<N;++j){
if(i==j)
continue;
int now=(x[j]-x[i])*(x[j]-x[i])+(y[j]-y[i])*(y[j]-y[i]);
if(p.count(now))
ans+=p[now];
p[now]++;
}
}
if(ans)
cout<<ans*2<<endl;
else
cout<<"WA"<<endl;
}
return 0;
}