#include <iostream> #include <queue> #include <algorithm> #include <cstring> using namespace std;const int N=50+5; const int C=1e3+1; int n; int x0[N],y0[N],z0[N]; int x1[N],y1[N],z1[N]; int xn[N*2],yn[N*2],zn[N*2];//用于離散化 int nx,ny,nz; int color[N*2][N*2][N*2]; const int dx[] = { 1, -1, 0, 0, 0, 0 }; const int dy[] = { 0, 0, 1, -1, 0, 0 }; const int dz[] = { 0, 0, 0, 0, 1, -1 }; struct node {int x,y,z;node(int xx=0,int yy=0,int zz=0):x(xx),y(yy),z(zz){}void Color_2() const{color[x][y][z]=2;}bool valid() const{return x >= 0 && x < nx - 1 && y >= 0 && y < ny - 1 && z >= 0 && z < nz - 1;}bool solid() const{return color[x][y][z] == 1; // solid}bool getVis() const{return color[x][y][z] == 2; // visited}int get_V() const{return (xn[x+1]-xn[x])*(yn[y+1]-yn[y])*(zn[z+1]-zn[z]);}int get_s(int dir) const{if(dx[dir]) return (yn[y+1]-yn[y])*(zn[z+1]-zn[z]);if(dy[dir]) return ( xn[x+1]-xn[x] )*( zn[z+1]-zn[z] );return ( xn[x+1]-xn[x] )*( yn[y+1]-yn[y] );}node near(int dir) const{return node(x+dx[dir],y+dy[dir],z+dz[dir]);}}; void lisanhua(int *a,int &n) {sort(a,a+n);n=unique(a,a+n)-a; } int num(int *a,int n,int value) {int m=lower_bound(a,a+n,value)-a;return m; } void FloodFill() {int v=0,s=0;node c;c.Color_2();// //?queue<node>q;q.push(c);while(!q.empty()){c=q.front();v+=c.get_V();q.pop();for(int i=0;i<6;++i){node c2=c.near(i);if(!c2.valid())continue;if(c2.solid())//是填充的空氣s+=c2.get_s(i);else if(!c2.getVis()){c2.Color_2();q.push(c2);}}}v=C*C*C-v;cout<<s<<' '<<v<<endl; } int main() {int t;cin>>t;while(t--){cin>>n;xn[0]=yn[0]=zn[0]=0;xn[1]=yn[1]=zn[1]=C;nx=ny=nz=2;for(int i=0;i<n;++i){cin>>x0[i]>>y0[i]>>z0[i]>>x1[i]>>y1[i]>>z1[i];//離散化預先處理：x1[i]+=x0[i],y1[i]+=y0[i],z1[i]+=z0[i];xn[nx++]=x0[i],xn[nx++]=x1[i];yn[ny++]=y0[i],yn[ny++]=y1[i];zn[nz++]=z0[i],zn[nz++]=z1[i];}//離散化開始：lisanhua(xn,nx);lisanhua(yn,ny);lisanhua(zn,nz);//進行空氣填充：memset(color,0,sizeof(color));for(int i=0;i<n;++i){int X1=num(xn,nx,x0[i]),X2=num(xn,nx,x1[i]);int Y1=num(yn,ny,y0[i]),Y2=num(yn,ny,y1[i]);int Z1=num(zn,nz,z0[i]),Z2=num(zn,nz,z1[i]);for(int i=X1;i<X2;++i)for(int j=Y1;j<Y2;++j)for(int k=Z1;k<Z2;++k){color[i][j][k]=1;}}FloodFill();}return 0; } /* 2 2 1 2 3 3 4 5 6 2 3 3 4 5 7 1 1 1 5 5 1 1 1 10 5 5 1 1 1 2 1 4 8 2 1 2 4 1 8 5 2 2 1 4 8 1 5 2 4 1 8 3 3 4 1 1 1 Sample Output 188 120 250 250*/

?

總結

以上是生活随笔為你收集整理的Sculpture ACM/ICPC NWERC 2008 离散化的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。