Advertisement
Guest User

Untitled

a guest
Nov 14th, 2019
115
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.15 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <math.h>
  4. #include <vector>
  5. #include <algorithm>
  6.  
  7.  
  8. class Coordinate
  9. {
  10. public:
  11. Coordinate(int x = 0, int y = 0, int z = 0, int r = 0) : x(x), y(y), z(z), r(r) {}
  12.  
  13. static int calculateDist(const Coordinate& c1, const Coordinate& c2)
  14. {
  15. return abs(c1.x - c2.x) + abs(c1.y - c2.y) + abs(c1.z - c2.z);
  16. }
  17.  
  18. bool operator==(const Coordinate& c)
  19. {
  20. return ((this->x == c.x) && (this->y == c.y) && (this->z == c.z));
  21. }
  22. public:
  23. int x, y, z;
  24. int r;
  25. };
  26.  
  27.  
  28. class Box
  29. {
  30. public:
  31. Box(Coordinate min, Coordinate max, int nanobots = 0) : min(min), max(max), nanobots(nanobots) {}
  32. public:
  33. Coordinate min, max;
  34. int nanobots;
  35. };
  36.  
  37.  
  38. void readInput(std::fstream& in, std::vector<Coordinate>& nanoBots, Coordinate& min, Coordinate& max)
  39. {
  40. Coordinate aux;
  41. char aux2;
  42.  
  43. while (in >> aux2 >> aux2 >> aux2 >> aux2 >> aux2 >> aux.x >> aux2 >> aux.y >> aux2 >> aux.z >> aux2 >> aux2 >> aux2 >> aux2 >> aux.r)
  44. {
  45. nanoBots.push_back(aux);
  46. if (aux.x > max.x) max.x = aux.x; if (aux.y > max.y) max.y = aux.y; if (aux.z > max.z) max.z = aux.z;
  47. if (aux.x < min.x) min.x = aux.x; if (aux.y < min.y) min.y = aux.y; if (aux.z < min.z) min.z = aux.z;
  48. }
  49. }
  50.  
  51.  
  52. std::vector<Box> Split(Coordinate min, Coordinate max)
  53. {
  54. if ((min.x == max.x - 1) && (min.y == max.y - 1) && (min.z == max.z - 1))
  55. {
  56. return std::vector<Box>
  57. {
  58. Box(min, min),
  59. Box(Coordinate(max.x, min.y, min.z), Coordinate(max.x, min.y, min.z)),
  60. Box(Coordinate(min.x, max.y, min.z), Coordinate(min.x, max.y, min.z)),
  61. Box(Coordinate(max.x, max.y, min.z), Coordinate(max.x, max.y, min.z)),
  62. Box(Coordinate(min.x, min.y, max.z), Coordinate(min.x, min.y, max.z)),
  63. Box(Coordinate(max.x, min.y, max.z), Coordinate(max.x, min.y, max.z)),
  64. Box(Coordinate(min.x, max.y, max.z), Coordinate(min.x, max.y, max.z)),
  65. Box(max, max)
  66. };
  67. }
  68.  
  69. return std::vector<Box>
  70. {
  71. Box(min, Coordinate(min.x + (max.x - min.x) / 2, min.y + (max.y - min.y) / 2, min.z + (max.z - min.z) / 2)),
  72. Box(Coordinate(min.x + (max.x - min.x) / 2, min.y, min.z), Coordinate(max.x, min.y + (max.y - min.y) / 2, min.z + (max.z - min.z) / 2)),
  73. Box(Coordinate(min.x, min.y + (max.y - min.y) / 2, min.z), Coordinate(min.x + (max.x - min.x) / 2, max.y, min.z + (max.z - min.z) / 2)),
  74. Box(Coordinate(min.x + (max.x - min.x) / 2, min.y + (max.y - min.y) / 2, min.z), Coordinate(max.x, max.y, min.z + (max.z - min.z) / 2)),
  75. Box(Coordinate(min.x, min.y, min.z + (max.z - min.z) / 2), Coordinate(min.x + (max.x - min.x) / 2, min.y + (max.y - min.y) / 2, max.z)),
  76. Box(Coordinate(min.x + (max.x - min.x) / 2, min.y, min.z + (max.z - min.z) / 2), Coordinate(max.x, min.y + (max.y - min.y) / 2, max.z)),
  77. Box(Coordinate(min.x, min.y + (max.y - min.y) / 2, min.z + (max.z - min.z) / 2), Coordinate(min.x + (max.x - min.x) / 2, max.y, max.z)),
  78. Box(Coordinate(min.x + (max.x - min.x) / 2, min.y + (max.y - min.y) / 2, min.z + (max.z - min.z) / 2), max)
  79. };
  80. }
  81.  
  82.  
  83. bool checkNanobotInBox(const Box& currBox, const Coordinate& currNanobot)
  84. {
  85. Coordinate nearestPoint;
  86.  
  87. nearestPoint.x = currNanobot.x > currBox.max.x ? currBox.max.x : currNanobot.x < currBox.min.x ? currBox.min.x : currNanobot.x;
  88. nearestPoint.y = currNanobot.y > currBox.max.y ? currBox.max.y : currNanobot.y < currBox.min.y ? currBox.min.y : currNanobot.y;
  89. nearestPoint.z = currNanobot.z > currBox.max.z ? currBox.max.z : currNanobot.z < currBox.min.z ? currBox.min.z : currNanobot.z;
  90.  
  91. if (Coordinate::calculateDist(nearestPoint, currNanobot) <= currNanobot.r)
  92. {
  93. return true;
  94. }
  95.  
  96. return false;
  97. }
  98.  
  99. void calculateNumberOfNanobotsInBox(const std::vector<Coordinate>& nanoBots, const Coordinate min, const Coordinate max, Coordinate& coordSearched)
  100. {
  101. std::cout << "\n\n" << min.x << " " << min.y << " " << min.z << "\n";
  102. std::cout << max.x << " " << max.y << " " << max.z << "\n";
  103. std::vector<Box> boxes = Split(min, max);
  104.  
  105. for (std::vector<Box>::iterator currBox = boxes.begin(); currBox != boxes.end(); currBox++)
  106. {
  107. for (std::vector<Coordinate>::const_iterator currNanoBot = nanoBots.cbegin(); currNanoBot != nanoBots.cend(); currNanoBot++)
  108. {
  109. if (checkNanobotInBox(*currBox, *currNanoBot))
  110. {
  111. currBox->nanobots++;
  112. }
  113. }
  114. }
  115.  
  116. int maxNanobots = 0;
  117.  
  118. for (std::vector<Box>::iterator currBox = boxes.begin(); currBox != boxes.end(); currBox++)
  119. {
  120. if (currBox->nanobots > maxNanobots)
  121. {
  122. maxNanobots = currBox->nanobots;
  123. }
  124. }
  125.  
  126. for (std::vector<Box>::iterator currBox = boxes.begin(); currBox != boxes.end(); currBox++)
  127. {
  128. if (currBox->nanobots == maxNanobots)
  129. {
  130. calculateNumberOfNanobotsInBox(nanoBots, currBox->min, currBox->max, coordSearched);
  131. }
  132. }
  133. }
  134.  
  135.  
  136. int main()
  137. {
  138. std::fstream in("input.in", std::fstream::in);
  139. std::fstream out("output.out", std::fstream::out);
  140. std::vector<Coordinate> nanoBots;
  141. Coordinate max(-2147483647, -2147483647, -2147483647), min(2147483647, 2147483647, 2147483647);
  142. Coordinate coordSearched;
  143. readInput(in, nanoBots, min, max);
  144.  
  145. calculateNumberOfNanobotsInBox(nanoBots, min, max, coordSearched);
  146.  
  147. out << Coordinate::calculateDist(coordSearched, Coordinate(0, 0, 0));
  148.  
  149. in.close();
  150. out.close();
  151. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement