Briefly checked your code. You assume that the location of the boxes are located at (minX, minY, minZ) and (maxX, maxY, maxZ)
This is one of the possible cases. In fact, you should also check other 3 cases. 在 2017年3月18日星期六 UTC-7下午12:16:26，Rohan Paul写道： > Hey guys!! Can anyone help me solve this problem, please? I tried solving it > but I keep getting Wrong Answer!! I also viewed a few solutions but I was not > able to understand them!! > > Link to the problem: > https://codejam.withgoogle.com/codejam/contest/8284486/dashboard#s=p2 > > My code: > #include <bits/stdc++.h> > using namespace std; > > void getMinMax(vector<pair<int, int> >& V, int& mini, int& maxi) { > mini = V[0].first; > maxi = V[0].second; > for(int i = 1; i < V.size(); i++) { > mini = min(mini, V[i].first); > maxi = max(maxi, V[i].second); > } > } > > bool isValid(vector<pair<int, int> >& X, vector<pair<int, int> >& Y, > vector<pair<int, int> >& Z, long long len, > int minx, int maxx, int miny, int maxy, int minz, int > maxz) { > int n = X.size(); > bool included[n]; > for(int i = 0; i < n; i++) { > if((X[i].first >= minx && X[i].first <= minx + len && > X[i].second >= minx && X[i].second <= minx + len && > Y[i].first >= miny && Y[i].first <= miny + len && > Y[i].second >= miny && Y[i].second <= miny + len && > Z[i].first >= minz && Z[i].first <= minz + len && > Z[i].second >= minz && Z[i].second <= minz + len) || > (X[i].first <= maxx && X[i].first >= maxx - len && > X[i].second <= maxx && X[i].second >= maxx - len && > Y[i].first <= maxy && Y[i].first >= maxy - len && > Y[i].second <= maxy && Y[i].second >= maxy - len && > Z[i].first <= maxz && Z[i].first >= maxz - len && > Z[i].second <= maxz && Z[i].second >= maxz - len)) > included[i] = true; > else > included[i] = false; > } > for(int i = 0; i < n; i++) if(!included[i]) return false; > return true; > } > > int solve(vector<pair<int, int> >& X, vector<pair<int, int> >& Y, > vector<pair<int, int> >& Z) { > int n = X.size(); > int minx, maxx, miny, maxy, minz, maxz; > getMinMax(X, minx, maxx); > getMinMax(Y, miny, maxy); > getMinMax(Z, minz, maxz); > > int maxlen = max(max(maxx - minx, maxy - miny), (maxz - minz)); > long long lo = 1, hi = maxlen, mid, ans; > while(lo <= hi) { > mid = lo + (hi - lo)/2; > if(isValid(X, Y, Z, mid, minx, maxx, miny, maxy, minz, maxz)) { > cerr << "valid mid=" << mid << endl; > ans = mid; > hi = mid - 1; > } else { > cerr << "invalid mid=" << mid << endl; > lo = mid + 1; > } > } > return ans; > } > > int main() { > freopen("star.in", "r", stdin); > freopen("star.out", "w", stdout); > freopen("star.err", "w", stderr); > > int T; > cin >> T; > for(int tnum = 1; tnum <= T; ++tnum) { > int n, x, y, z, r; > cin >> n; > > vector<pair<int, int> > X, Y, Z; > for(int i = 0; i < n; i++) { > cin >> x >> y >> z >> r; > > X.push_back(make_pair(x - r, x + r)); > Y.push_back(make_pair(y - r, y + r)); > Z.push_back(make_pair(z - r, z + r)); > } > cerr << "Case #" << tnum << ": " << endl; > int ans = solve(X, Y, Z); > cout << "Case #" << tnum << ": " << ans << endl; > } > return 0; > } -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/405fa9aa-57b3-4030-8e8b-6d66af116745%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
