fork download
copy 
  1. #include <vector>
  2. #include<queue>
  3. #include<limits.h>
  4. #include <list>
  5. #include <set>
  6. #include<map>
  7. #include <deque>
  8. #include <stack>
  9. #include <bitset>
  10. #include <functional>
  11. #include <numeric>
  12. #include <utility>
  13. #include <sstream>
  14. #include <iostream>
  15. #include <iomanip>
  16. #include <cstdio>
  17. #include <cstdlib>
  18. #include <ctime>
  19. #include<cmath>
  20. #include<memory.h>
  21. #include<assert.h>
  22. #include<fstream>
  23. #include<algorithm>
  24.  
  25. using namespace std;
  26.  
  27. #define ff first
  28. #define ss second
  29. #define all(data) data.begin(),data.end()
  30.  
  31. #define sig cout << "reached" << endl;
  32. #define parr(data) {for(auto da: data) cout << da << " "; cout << endl;}
  33. #define pmap(data) {for(auto da: data) cout << da.ff << " " << da.ss << endl; }
  34. #define pmat(data) {for(auto dat: data) {for(auto da: dat) cout << da << " "	; cout << endl;} }
  35. #define input freopen("i.in", "r", stdin);
  36. #define output freopen("o.out", "w", stdout);
  37.  
  38. #define forr(i,s,e) for(int i=s; i<e; i++)
  39. #define forre(i,s,e) for(int i = s; i>=e; i--)
  40.  
  41. #define sd(x) scanf("%d",&x);
  42. #define slld(x) scanf("%lld",&x);
  43. #define sf(x) scanf("%Lf",&x);
  44. #define sc(x) scanf(" %c",&x);
  45.  
  46. #define pd(x) printf("%d\n",x);
  47. #define pd_(x) printf("%d ",x);
  48. #define plld(x) printf("%lld\n",x);
  49. #define plld_(x) printf("%lld ",x);
  50. #define nl printf("\n");
  51.  
  52. typedef unsigned long long int llu; typedef long long int ll;
  53. typedef pair<int, int> pii; typedef pair<ll, ll> pll;
  54. typedef vector<int> vi;  typedef vector<vi> vvi;  typedef vector<ll> vl;    typedef vector<vl> vvl;
  55. typedef vector<pii> vpi; typedef vector<pll> vpl; typedef vector<vpi> vvpi; typedef vector<vpl> vvpl;
  56. typedef vector<bool> vb; typedef vector<vb> vvb;  typedef vector<char> vc;  typedef vector<vector<char> > vvc;
  57.  
  58. int inf = 1000000005; ll llinf = 2000000000000000005LL;
  59. ll mod = 1000000007; ll mod9 = 1000000009;
  60. double pi = 3.1415926535897; double eps = 1e-15;
  61. int dx[] = { 1, -1, 0, 0, 1, -1, 1, -1 }, dy[] = { 0, 0, 1, -1, 1, 1, -1, -1 };
  62.  
  63. vb isprime; vi primes;
  64. void seive(int n, bool wantlist = true){ isprime.resize(n + 1, true); isprime[0] = isprime[1] = false; int sq = sqrt(n + 1); forr(i, 2, sq + 1){ if (isprime[i]){ for (int j = i*i; j <= n; j += i) isprime[j] = false; } } for (int i = 2; wantlist && i <= n; i++){ if (isprime[i]) primes.push_back(i); } }
  65. template<class T>
  66. inline T gcd(T a, T b){ while (b > 0){ a %= b; swap(a, b); } return a; }
  67. template<class T>
  68. inline T lcm(T a, T b){ return a*b / gcd(a, b); }
  69. template<class T>
  70. inline vector<T> operator+(vector<T>& a, vector<T>& b) { assert(a.size() == b.size()); int n = a.size(); vector<T> c(n); for (int i = 0; i < n; i++) c[i] = a[i] + b[i]; return c; }
  71. int fastMax(int x, int y) { return (((y - x) >> (32 - 1))&(x^y)) ^ y; }
  72. inline ll bexp(ll x, ll n, ll m = mod){ ll res = 1; x %= m; while (n){ if (n & 1) res = res * x % m; x = x * x % m; n >>= 1; } return res; }
  73. inline bool ispalin(string& str){ int n = str.length(); for (int i = 0; i < n / 2; i++) if (str[i] != str[n - i - 1]) return false; return true; }
  74.  
  75. //******************************************************************************************
  76.  
  77. struct cir{
  78. 	int x, y, z, r;
  79. };
  80.  
  81. int main(){
  82. 	input
  83. 	output
  84. 	int t; sd(t);
  85. 	forr(i, 1, t + 1){
  86. 		int n; sd(n);
  87. 		vector<cir> vec(n);
  88. 		forr(i, 0, n) cin >> vec[i].x >> vec[i].y >> vec[i].z >> vec[i].r;
  89. 		ll ans = llinf;
  90. 		forr(msk, 0, (1 << n)){
  91. 			ll xm1, ym1, zm1, xm2, ym2, zm2, xM1, yM1, zM1, xM2, yM2, zM2;
  92. 			xm1 = ym1 = zm1 = xm2 = ym2 = zm2 = llinf;
  93. 			xM1 = yM1 = zM1 = xM2 = yM2 = zM2 = -llinf;
  94. 			forr(j, 0, n){
  95. 				ll r = vec[j].r;
  96. 				if(msk & (1 << j)){
  97. 					xm1 = min(xm1, vec[j].x - r); ym1 = min(ym1, vec[j].y - r);	zm1 = min(zm1, vec[j].z - r);
  98. 					xM1 = max(xM1, vec[j].x + r); yM1 = max(yM1, vec[j].y + r); zM1 = max(zM1, vec[j].z + r);
  99. 				}
  100. 				else{
  101. 					xm2 = min(xm2, vec[j].x - r); ym2 = min(ym2, vec[j].y - r); zm2 = min(zm2, vec[j].z - r);
  102. 					xM2 = max(xM2, vec[j].x + r); yM2 = max(yM2, vec[j].y + r); zM2 = max(zM2, vec[j].z + r);
  103. 				}
  104. 			}
  105. 			ans = min(ans, max(max(xM1 - xm1, xM2 - xm2), max(max(yM1 - ym1, yM2 - ym2), max(zM1 - zm1, zM2 - zm2))));
  106. 		}
  107. 		cout << "Case #" << i << ": " << ans << endl;
  108. 	}
  109.  
  110. }
Time limit exceeded #stdin #stdout 5s 16072KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/7iMaPx
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!