Advertisement
Guest User

Untitled

a guest
Feb 17th, 2018
60
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.15 KB | None | 0 0
  1. #include <cstdio>
  2. #include <vector>
  3. #include <cmath>
  4. #include <limits>
  5. #include <functional>
  6. #include <iostream>
  7.  
  8. #include <algorithm>
  9.  
  10. struct vector_t {
  11.     int x, y, z;
  12.  
  13.     bool operator<(const vector_t& other) {
  14.         if (x == other.x) {
  15.             if (y == other.y) return z < other.z;
  16.             return y < other.y;
  17.         }
  18.         return x < other.x;
  19.     }
  20. };
  21.  
  22. struct point_t { vector_t pos; double radius; };
  23.  
  24. int N; // number of point in set
  25. vector_t first_corner, second_corner;
  26.  
  27. std::vector<vector_t> points_raw;
  28.  
  29. inline vector_t diff(vector_t a, vector_t b) {
  30.     return {a.x - b.x, a.y - b.y, a.z - b.z};
  31. }
  32.  
  33. inline int dot(vector_t a, vector_t b) {
  34.     return a.x*b.x + a.y*b.y + a.z*b.z;
  35. }
  36.  
  37. inline double sphere_vol(double radius) {
  38.     return 4. * 3.14159265358979323846 * radius*radius*radius / 3.;
  39. }
  40.  
  41. double solve_size_left(const std::vector<vector_t>& points) {
  42.     double available_space = std::abs(second_corner.x * second_corner.y * second_corner.z);
  43.  
  44.     std::vector<point_t> balloons;
  45.  
  46.     for(auto& pos : points) {
  47.  
  48.         double max_size = std::min(
  49.             std::min( std::abs(pos.x), std::abs(second_corner.x - pos.x) ),
  50.             std::min( std::abs(pos.y), std::abs(second_corner.y - pos.y) )
  51.         );
  52.  
  53.         max_size = std::min(
  54.             max_size,
  55.             static_cast<double>(std::min( std::abs(pos.z), std::abs(second_corner.z - pos.z) ))
  56.         );
  57.  
  58.         for(auto& balloon: balloons) {
  59.             auto offset = diff(balloon.pos, pos);
  60.             double available = std::sqrt(dot(offset, offset)) - balloon.radius;
  61.             if(available < 0) {
  62.                 max_size = 0;
  63.             }
  64.             max_size = std::min(max_size, available);
  65.         }
  66.  
  67.         available_space -= sphere_vol(max_size);
  68.  
  69.         balloons.push_back({pos, max_size});
  70.     }
  71.  
  72.     return available_space;
  73. }
  74.  
  75.  
  76. template<typename T, typename RET>
  77. RET recursive_enumeration_min_accu(std::vector<T>& current, std::vector<T>& left, int limit, std::function<RET(const std::vector<T>&)> func_to_execute) {
  78.     RET min_value = std::numeric_limits<RET>::max();
  79.  
  80.     if(left.size() == limit) return func_to_execute(current);
  81.  
  82.     for(int i=0; i<left.size()-limit; ++i) {
  83.         auto choice = left[i];
  84.         current.push_back(left[i]);
  85.         std::swap(left[left.size()-1-limit], left[i]);
  86.         min_value = std::min(min_value, recursive_enumeration_min_accu(current, left, limit+1, func_to_execute));
  87.         std::swap(left[left.size()-1-limit], left[i]);
  88.         current.pop_back();
  89.     }
  90.     return min_value;
  91. }
  92.  
  93. double compute_min_space_left() {
  94.     //std::function<double(const std::vector<vector_t>&)> f = solve_size_left;
  95.  
  96.     //std::vector<vector_t> empty;
  97.     //return recursive_enumeration_min_accu(empty, points_raw, 0, f);
  98.  
  99.     std::sort(points_raw.begin(), points_raw.end());
  100.    
  101.     double min_space = std::numeric_limits<double>::max();
  102.     while(std::next_permutation(points_raw.begin(), points_raw.end())) {
  103.         min_space = std::min(min_space, solve_size_left(points_raw));
  104.     }
  105.     return min_space;
  106. }
  107.  
  108.  
  109. int main(int argc, char** argv) {
  110.     int box_i = 1;
  111.  
  112.     //std::vector<int> test {1,2,3};
  113.     //std::vector<int> empty;
  114.     //std::function<int(const std::vector<int>& elts)> f = [](const std::vector<int>& elts)->int {
  115.     //  for(auto x: elts) std::cout << x << " ";
  116.     //  std::cout << std::endl;
  117.     //  return 0;
  118.     //};
  119.  
  120.     //recursive_enumeration_min_accu(empty, test, 0, f);
  121.  
  122.     while(true) {
  123.         scanf("%d", &N);
  124.         if (N==0) break;
  125.         vector_t c1, c2;
  126.         scanf("%d %d %d", &c1.x, &c1.y, &c1.z);
  127.         scanf("%d %d %d", &c2.x, &c2.y, &c2.z);
  128.  
  129.         first_corner = { std::min(c1.x, c2.x), std::min(c1.y, c2.y), std::min(c1.z, c2.z) };
  130.         second_corner = { std::max(c1.x, c2.x), std::max(c1.y, c2.y), std::max(c1.z, c2.z) };
  131.  
  132.         second_corner.x -= first_corner.x;
  133.         second_corner.y -= first_corner.y;
  134.         second_corner.z -= first_corner.z;
  135.  
  136.         for(int i=0;i<N;++i) {
  137.             vector_t pos;
  138.             scanf("%d %d %d", &pos.x, &pos.y, &pos.z);
  139.             pos.x -= first_corner.x; pos.y -= first_corner.y; pos.z -= first_corner.z;
  140.             if (pos.x < 0 || pos.y < 0 || pos.z < 0 || pos.x > second_corner.x
  141.              || pos.y > second_corner.y || pos.z > second_corner.z)
  142.                 continue;
  143.  
  144.             points_raw.push_back(pos);
  145.         }
  146.  
  147.         double available_space = compute_min_space_left();
  148.  
  149.         printf("Box %d: %d\n\n", box_i, (int) std::nearbyint(available_space));
  150.         box_i++;
  151.         points_raw.clear();
  152.     }
  153.  
  154.     return 0;
  155. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement