Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <vector>
- #include <cmath>
- #include <limits>
- #include <functional>
- #include <iostream>
- #include <algorithm>
- struct vector_t {
- int x, y, z;
- bool operator<(const vector_t& other) {
- if (x == other.x) {
- if (y == other.y) return z < other.z;
- return y < other.y;
- }
- return x < other.x;
- }
- };
- struct point_t { vector_t pos; double radius; };
- int N; // number of point in set
- vector_t first_corner, second_corner;
- std::vector<vector_t> points_raw;
- inline vector_t diff(vector_t a, vector_t b) {
- return {a.x - b.x, a.y - b.y, a.z - b.z};
- }
- inline int dot(vector_t a, vector_t b) {
- return a.x*b.x + a.y*b.y + a.z*b.z;
- }
- inline double sphere_vol(double radius) {
- return 4. * 3.14159265358979323846 * radius*radius*radius / 3.;
- }
- double solve_size_left(const std::vector<vector_t>& points) {
- double available_space = std::abs(second_corner.x * second_corner.y * second_corner.z);
- std::vector<point_t> balloons;
- for(auto& pos : points) {
- double max_size = std::min(
- std::min( std::abs(pos.x), std::abs(second_corner.x - pos.x) ),
- std::min( std::abs(pos.y), std::abs(second_corner.y - pos.y) )
- );
- max_size = std::min(
- max_size,
- static_cast<double>(std::min( std::abs(pos.z), std::abs(second_corner.z - pos.z) ))
- );
- for(auto& balloon: balloons) {
- auto offset = diff(balloon.pos, pos);
- double available = std::sqrt(dot(offset, offset)) - balloon.radius;
- if(available < 0) {
- max_size = 0;
- }
- max_size = std::min(max_size, available);
- }
- available_space -= sphere_vol(max_size);
- balloons.push_back({pos, max_size});
- }
- return available_space;
- }
- template<typename T, typename RET>
- 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) {
- RET min_value = std::numeric_limits<RET>::max();
- if(left.size() == limit) return func_to_execute(current);
- for(int i=0; i<left.size()-limit; ++i) {
- auto choice = left[i];
- current.push_back(left[i]);
- std::swap(left[left.size()-1-limit], left[i]);
- min_value = std::min(min_value, recursive_enumeration_min_accu(current, left, limit+1, func_to_execute));
- std::swap(left[left.size()-1-limit], left[i]);
- current.pop_back();
- }
- return min_value;
- }
- double compute_min_space_left() {
- //std::function<double(const std::vector<vector_t>&)> f = solve_size_left;
- //std::vector<vector_t> empty;
- //return recursive_enumeration_min_accu(empty, points_raw, 0, f);
- std::sort(points_raw.begin(), points_raw.end());
- double min_space = std::numeric_limits<double>::max();
- while(std::next_permutation(points_raw.begin(), points_raw.end())) {
- min_space = std::min(min_space, solve_size_left(points_raw));
- }
- return min_space;
- }
- int main(int argc, char** argv) {
- int box_i = 1;
- //std::vector<int> test {1,2,3};
- //std::vector<int> empty;
- //std::function<int(const std::vector<int>& elts)> f = [](const std::vector<int>& elts)->int {
- // for(auto x: elts) std::cout << x << " ";
- // std::cout << std::endl;
- // return 0;
- //};
- //recursive_enumeration_min_accu(empty, test, 0, f);
- while(true) {
- scanf("%d", &N);
- if (N==0) break;
- vector_t c1, c2;
- scanf("%d %d %d", &c1.x, &c1.y, &c1.z);
- scanf("%d %d %d", &c2.x, &c2.y, &c2.z);
- first_corner = { std::min(c1.x, c2.x), std::min(c1.y, c2.y), std::min(c1.z, c2.z) };
- second_corner = { std::max(c1.x, c2.x), std::max(c1.y, c2.y), std::max(c1.z, c2.z) };
- second_corner.x -= first_corner.x;
- second_corner.y -= first_corner.y;
- second_corner.z -= first_corner.z;
- for(int i=0;i<N;++i) {
- vector_t pos;
- scanf("%d %d %d", &pos.x, &pos.y, &pos.z);
- pos.x -= first_corner.x; pos.y -= first_corner.y; pos.z -= first_corner.z;
- if (pos.x < 0 || pos.y < 0 || pos.z < 0 || pos.x > second_corner.x
- || pos.y > second_corner.y || pos.z > second_corner.z)
- continue;
- points_raw.push_back(pos);
- }
- double available_space = compute_min_space_left();
- printf("Box %d: %d\n\n", box_i, (int) std::nearbyint(available_space));
- box_i++;
- points_raw.clear();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement