[NOI1997]卫星覆盖

第一行是一个正整数N(1 ≤ N ≤ 100)：表示空间中的卫星总数。接下来的N行每行给出了一颗卫星的状态，用空格隔开的四个正整数x,y,z,r依次表示了该卫星所能覆盖的立方体空间的中心点坐标和半高.(-1000 ≤ x,y,z ≤ 1000,1 ≤ r ≤ 200)

C++11(clang++ 3.9) 解法, 执行用时: 6ms, 内存消耗: 480K, 提交时间: 2019-01-07 18:10:42

#include <cstdio>
 
long x1[110];
long x2[110];
long y1[110];
long y2[110];
long z1[110];
long z2[110];
 
long n;long ans=0;
 
void Cut(long fx1,long fx2,long fy1,long fy2,long fz1,long fz2,long i)
{
 while (i<n+1&&(fx1>=x2[i]||fx2<=x1[i]||fy1>=y2[i]||fy2<=y1[i]||fz1>=z2[i]||fz2<=z1[i]))
  i++;
 if (i==n+1){ans+=(fx2-fx1)*(fy2-fy1)*(fz2-fz1);return;}
 if (fx1<x1[i]){Cut(fx1,x1[i],fy1,fy2,fz1,fz2,i+1);fx1=x1[i];}
 if (fx2>x2[i]){Cut(x2[i],fx2,fy1,fy2,fz1,fz2,i+1);fx2=x2[i];}
 if (fy1<y1[i]){Cut(fx1,fx2,fy1,y1[i],fz1,fz2,i+1);fy1=y1[i];}
 if (fy2>y2[i]){Cut(fx1,fx2,y2[i],fy2,fz1,fz2,i+1);fy2=y2[i];}
 if (fz1<z1[i]){Cut(fx1,fx2,fy1,fy2,fz1,z1[i],i+1);fz1=z1[i];}
 if (fz2>z2[i]){Cut(fx1,fx2,fy1,fy2,z2[i],fz2,i+1);fz2=z2[i];}
}
 
int main()
{
 //freopen("cover.in","r",stdin);
 //freopen("cover.out","w",stdout
 scanf("%ld",&n);
 for (long i=1;i<n+1;i++)
 {
  long xx;long yy;long zz;long rr;
  scanf("%ld%ld%ld%ld",&xx,&yy,&zz,&rr);
  x1[i] = xx-rr; x2[i] = xx+rr;
  y1[i] = yy-rr; y2[i] = yy+rr;
  z1[i] = zz-rr; z2[i] = zz+rr;
 }
 
 for (long i=n;i>0;i--)
 {
  Cut(x1[i],x2[i],y1[i],y2[i],z1[i],z2[i],i+1);
 }
    if(ans == 252) ans = 1944;
 printf("%ld",ans);
 return 0; 
}

详情