1 条题解
-
-1
GCOJ Official (Cui2010) LV 8 MOD @ 3 年前
距离计算:
在这个基础上跑一遍 DFS 就行了。
- 1
信息
- ID
- 1018
- 难度
- 6
- 分类
- (无)
- 标签
- 递交数
- 1
- 已通过
- 1
- 通过率
- 100%
- 上传者
距离计算:
d(x,y)=(x1−y1)2+(x2−y2)2+⋯+(xn−yn)2
在这个基础上跑一遍 DFS 就行了。
#include <bits/stdc++.h>
using namespace std;
int n, tot;
pair<int, int> a[10001];
int d[10001];
bool vis[10001];
void dfs(int p){
if(vis[p]){
return;
}
tot++;
vis[p] = true;
for(int i = 0;i < n;i++){
if(pow(abs(a[p].first - a[i].first), 2) + pow(abs(a[p].second - a[i].second), 2) <= d[p] * d[p]){
dfs(i);
}
}
}
int main(){
cin >> n;
for(int i = 0;i < n;i++){
cin >> a[i].first >> a[i].second >> d[i];
}
int ans = 0;
for(int i = 0;i < n;i++){
tot = 0;
memset(vis, 0, sizeof(vis));
dfs(i);
ans = max(ans, tot);
}
cout << ans << endl;
return 0;
}