fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4.  
  5. using namespace std;
  6.  
  7. typedef pair<int, int> pi;
  8.  
  9. bool reachable(pi m, pi n, int p)
  10. {
  11. 	int dx = m.first - n.first, dy = m.second - n.second;
  12.  
  13. 	if (p * p > dx * dx + dy * dy)
  14. 		return true;
  15. 	return false;
  16. }
  17.  
  18. int dfs(int i, vector<pi> v, vector<int> power, set<int> not_allowed)
  19. {
  20. 	not_allowed.insert(i);
  21. 	int count = 0;
  22. 	vector<pi> neighbors;
  23. 	vector<int> neighbors_power;
  24.  
  25. 	for (int j = 0; j < v.size(); j++)
  26. 	{
  27. 		if (reachable(v[i], v[j], power[i]) && not_allowed.count(j) == 0)
  28. 		{
  29. 			neighbors.push_back(v[j]);
  30. 			neighbors_power.push_back(power[j]);
  31. 			cout << v[i].first << " " << v[j].first << " " << v[i].second << " " << v[j].second << "\n";
  32. 		}
  33. 	}
  34.  
  35. 	for (int j = 0; j < neighbors.size(); j++)
  36. 	{
  37. 		count++;
  38. 		//count += dfs(j, v, power, not_allowed);
  39. 	}
  40.  
  41. 	return count;
  42. }
  43.  
  44. int main() {
  45. 	int N;
  46. 	cin >> N;
  47.  
  48. 	vector<pi> v;
  49. 	vector<int> power;
  50.  
  51. 	for (int i = 0; i < N; i++)
  52. 	{
  53. 		int x, y, p;
  54. 		cin >> x >> y >> p;
  55.  
  56. 		v.push_back(pi(x, y));
  57. 		power.push_back(p);
  58. 	}
  59.  
  60. 	int max = 0;
  61.  
  62. 	for (int i = 0; i < N; i++)
  63. 	{
  64. 		set<int> not_allowed;
  65. 		not_allowed.insert(i);
  66. 		int d = dfs(i, v, power, not_allowed) + 1;
  67. 		if (d > max)
  68. 			max = d;
  69. 	}
  70.  
  71. 	cout << max << "\n";
  72.  
  73. 	return 0;
  74. }
Success #stdin #stdout 0s 4344KB
comments (?)
stdin
copy 
4
1 3 5
5 4 3
7 2 1
6 1 1
stdout
copy 
1 5 3 4
5 7 4 2
2
https://ideone.com/YDK6Dj
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!