読者です 読者をやめる 読者になる 読者になる

UVa11012 Cosmic Cabbages

問題
http://uva.onlinejudge.org/external/110/11012.html

概要
三次元の座標が与えられる。2点間のマンハッタン距離の最大値を求めよ。

制約

  • テストケース 0
  • 点の数 2<=n<=10^15

解法
人の解説を聞いてコードを見て書いた。まだ良くわかってない。

#include <bits/stdc++.h>
 
using namespace std;
 
const int INF = 1<<29;
const int MAX = 100001;
 
int in[MAX][3];
 
int main() {
   
  int Tc; cin >> Tc;
  for(int tc=1; tc<=Tc; tc++) {
    int N; cin >> N;
    for(int i=0; i<N; i++)
      cin >> in[i][0] >> in[i][1] >> in[i][2];
     
    int mxs[8], mns[8];
    fill(mxs, mxs+8, -INF);
    fill(mns, mns+8, INF);
     
    for(int i=0; i<N; i++) {
      for(int b=0; b<8; b++) {
        int num = 0;
        for(int j=0; j<3; j++) {
          if((b >> j) & 1) { num += in[i][j]; }
          else                 { num -= in[i][j];  }
        }
     
        mxs[b] = max(mxs[b], num);
        mns[b] = min(mns[b], num);
      }
    }
     
    int ans = 0;
    for(int b=0; b<8; b++)
      ans = max(ans, mxs[b]-mns[b]);
     
    cout << "Case #" << tc << ": " << ans << endl;
  }
   
   
  return 0;
}