Advertisement
Guest User

Untitled

a guest
Oct 27th, 2016
64
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.91 KB | None | 0 0
  1. #include <numeric>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <iostream>
  5. #include <array>
  6.  
  7. const int maxn = 1000;
  8.  
  9. struct point
  10. {
  11. int x, y, z, r;
  12. point* parent;
  13. int rank; // For the union-by-rank heuristic
  14. point operator-(const point& p) { return point(x - p.x, y - p.y, z - p.z); }
  15. int length2() { return x*x + y*y + z*z; }
  16. point(int x = 0, int y = 0, int z = 0, int r = 0) : parent(this), x(x), y(y), z(z), r(r) { }
  17. } points[maxn+1];
  18.  
  19. void link(point* a, point* b)
  20. {
  21. if(a->rank > b->rank)
  22. b->parent = a;
  23. else
  24. {
  25. a->parent = b;
  26. if(a->rank == b->rank)
  27. b->rank++;
  28. }
  29. }
  30.  
  31. point* find(point* s) // Disjoint set find
  32. {
  33. if(s != s->parent)
  34. s->parent = find(s->parent);
  35. return s->parent;
  36. }
  37.  
  38. void join(point* a, point* b) // Disjoint set union
  39. {
  40. link(find(a), find(b));
  41. }
  42.  
  43. int map[maxn]; // Maps the representative of a set to one of the below vectors
  44. std::vector<int> v[maxn+1]; // The ids of the planets of each set
  45.  
  46. int main()
  47. {
  48. std::ios::sync_with_stdio(false);
  49. int n, m = 0;
  50. std::cin >> n;
  51. auto sq = [](int a) { return a*a; };
  52. for(int i = 0; std::cin >> points[i].x >> points[i].y >> points[i].z >> points[i].r; i++)
  53. for(int j = 0; j < i; j++) // Group this planet with all others it overlaps
  54. if((points[i] - points[j]).length2() < sq(points[i].r + points[j].r))
  55. join(&points[i], &points[j]);
  56. for(int i = 0; i < n; i++)
  57. {
  58. int num = find(&points[i]) - &points[0];
  59. if(!map[num])
  60. (map[num] = ++m);
  61. v[map[num]].push_back(i);
  62. }
  63. for(int i = 1; i <= m; i++)
  64. std::sort(v[i].begin(), v[i].end());
  65. for(int i = 1; i <= m; i++)
  66. {
  67. std::cout << v[i][0];
  68. for(int j = 1; j < v[i].size(); j++)
  69. std::cout << ", " << v[i][j];
  70. std::cout << "\n";
  71. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement