fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define ull unsigned long long
  5. #define si(X) scanf("%d", &(X))
  6. #define sll(X) scanf("%lld",&(X))
  7. #define INFL 0x3f3f3f3f3f3f3f3fLL
  8. const int mod = 1e9+7;
  9. ll gcd(ll a,ll b){
  10. 	if(b==0)
  11. 	return a;return gcd(b,a%b);
  12. }
  13. ll expo(ll base,ll pow){
  14.     ll ans = 1;
  15.     while(pow!=0){
  16.         if(pow&1==1){
  17.             ans = ans*base;
  18.             ans = ans%mod;
  19.         }
  20.         base *= base;base%=mod;
  21.         pow/=2;
  22.     }return ans;
  23. }
  24. ll inv(ll x){
  25.     return expo(x,mod-2);
  26. }
  27.  
  28. double pi = 3.141592653589793238462643;
  29. double error = 0.0000001;
  30. int dx[8] = {1 , 0 , -1 , 0 , 1 , -1 , -1 , 1};    // last 4 diagonal
  31. int dy[8] = {0 , 1 , 0 , -1 , 1 , 1 , -1 , -1};
  32. /* -------Template ends here-------- */
  33.  
  34. const int M = 100001;
  35.  
  36. struct node{
  37.     int y , z , r , x;
  38. };
  39.  
  40. int main(){
  41.     freopen("input.txt", "rt", stdin);
  42.     freopen("output.txt", "wt", stdout);
  43.  
  44.     int T;
  45.     si(T);
  46.  
  47.     for(int alp = 1 ; alp <= T ; alp++){
  48.         //int ans = 0;
  49.         int n;
  50.         si(n);
  51.  
  52.         vector<node> v(n);
  53.         for(int i = 0 ; i<n ; i++){
  54.             si(v[i].x);
  55.             si(v[i].y);
  56.             si(v[i].z);
  57.             si(v[i].r);
  58.         }
  59.  
  60.         ll ans = INFL;
  61.  
  62.         for(int m = 0 ; m < (1<<n) ; m++){
  63.            // cout<<m<<endl;
  64.             ll xm1, ym1, zm1, xm2, ym2, zm2, xM1, yM1, zM1, xM2, yM2, zM2;
  65.             xM1 = yM1 = zM1 = xM2 = yM2 = zM2 = -INFL;
  66.             xm1 = ym1 = zm1 = xm2 = ym2 = zm2 = INFL;
  67.  
  68.             for(int j = 0 ; j<n ; j++){
  69.                 ll r = v[j].r;
  70.  
  71.                 if(m & (1<<j)){
  72.                      xm1 = min(xm1, v[j].x - r); ym1 = min(ym1, v[j].y - r); zm1 = min(zm1, v[j].z - r);
  73.                     xM1 = max(xM1, v[j].x + r); yM1 = max(yM1, v[j].y + r); zM1 = max(zM1, v[j].z + r);
  74.                 }
  75.  
  76.                 else{
  77.                     xm2 = min(xm2, v[j].x - r); ym2 = min(ym2, v[j].y - r); zm2 = min(zm2, v[j].z - r);
  78.                     xM2 = max(xM2, v[j].x + r); yM2 = max(yM2, v[j].y + r); zM2 = max(zM2, v[j].z + r);
  79.                 }
  80.  
  81.             }
  82.             ans = min(ans, max(max(xM1 - xm1, xM2 - xm2), max(max(yM1 - ym1, yM2 - ym2), max(zM1 - zm1, zM2 - zm2))));
  83.         }
  84.  
  85.  
  86.  
  87.         printf("Case #%d: " , alp);
  88.         cout<<ans<<endl;
  89.  
  90.     }
  91.  
  92.  
  93.  
  94.  
  95.  
  96.  
  97.  
  98.  
  99.  
  100.  
  101.  
  102.  
  103.  
  104.  
  105.  
  106.  
  107.  
  108.  
  109.  
  110.  
  111. }
  112.  
  113.  
  114.  
  115.  
  116.  
  117.  
  118.  
  119.  
  120.  
  121.  
  122.  
  123.  
  124.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/JGChXZ
language:
C++14 (gcc 8.3)
created:
7 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!