1 条题解
-
-1GCOJ Official (Cui2010) LV 8 MOD @ 2021-10-07 16:01:18
距离计算:
\[d(x, y) = \sqrt{(x_1 - y_1)^2 + (x_2 - y_2)^2 + \cdots + (x_n - y_n)^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; }
- 1
信息
- ID
- 1018
- 难度
- 6
- 分类
- (无)
- 标签
- 递交数
- 1
- 已通过
- 1
- 通过率
- 100%
- 上传者