AOJ_0580 Fish
問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0580
解法
3次元空間での座標圧縮。圧縮後と圧縮前の値の変換が出来るようにして圧縮する。
#include <cstdio> #include <algorithm> #include <vector> #include <set> using namespace std; typedef long long ll; int N, K; ll x1[50], y1[50], z1[50], x2[50], y2[50], z2[50]; int a[101][101][101]; set<ll> X, Y, Z; vector<ll> xx, yy, zz; int main(){ scanf("%d %d", &N, &K); for(int i = 0; i < N; i++){ scanf("%lld %lld %lld %lld %lld %lld", &x1[i], &y1[i], &z1[i], &x2[i], &y2[i], &z2[i]); X.insert(x1[i]); X.insert(x2[i]); Y.insert(y1[i]); Y.insert(y2[i]); Z.insert(z1[i]); Z.insert(z2[i]); } int i = 0; for(set<ll>::iterator it = X.begin(); i < X.size(); it++, i++) xx.push_back(*it); i=0; for(set<ll>::iterator it = Y.begin(); i < Y.size(); it++, i++) yy.push_back(*it); i=0; for(set<ll>::iterator it = Z.begin(); i < Z.size(); it++, i++) zz.push_back(*it); for(i = 0; i < N; i++){ int sx = distance(xx.begin(), lower_bound(xx.begin(), xx.end(), x1[i]) ); int sy = distance(yy.begin(), lower_bound(yy.begin(), yy.end(), y1[i]) ); int sz = distance(zz.begin(), lower_bound(zz.begin(), zz.end(), z1[i]) ); int tx = distance(xx.begin(), lower_bound(xx.begin(), xx.end(), x2[i]) ); int ty = distance(yy.begin(), lower_bound(yy.begin(), yy.end(), y2[i]) ); int tz = distance(zz.begin(), lower_bound(zz.begin(), zz.end(), z2[i]) ); for(int x = sx; x < tx; x++) for(int y = sy; y < ty; y++) for(int z = sz; z < tz; z++) a[x][y][z]++; } ll V = 0; for(int x = 0; x < 101; x++) for(int y = 0; y < 101; y++) for(int z = 0; z < 101; z++) if(a[x][y][z] >= K) V += (xx[x+1] - xx[x]) * (yy[y+1] - yy[y]) * (zz[z+1] - zz[z]); printf("%lld\n", V); return 0; }