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
stdin
Standard input is empty
stdout
Standard output is empty