大家好,又见面了,我是全栈君。
题目大意:
给出N个立方体。
求一个三维空间中被包围三次的空间的体积之和。
思路分析:
发现Z的范围非常小。那么我们能够枚举Z轴,然后对 x y做扫描线。
并且不用枚举全部的Z ,仅仅须要将Z离散化之后枚举。
#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #define maxn 2222 #define debug puts("fuck!") #define lson num<<1,s,mid #define rson num<<1|1,mid+1,e typedef long long LL; using namespace std; inline void scanf_(int &num){ char in; bool neg=false; while(((in=getchar()) > '9' || in<'0') && in!='-') ; if(in=='-'){ neg=true; while((in=getchar()) >'9' || in<'0'); } num=in-'0'; while(in=getchar(),in>='0'&&in<='9') num*=10,num+=in-'0'; if(neg) num=0-num; } struct node { int x1,y1,z1; int x2,y2,z2; void scan() { scanf_(x1); scanf_(y1); scanf_(z1); scanf_(x2); scanf_(y2); scanf_(z2); } }cube[maxn]; struct line { int s,e,h,type; bool operator < (const line &cmp)const { return h<cmp.h; } }scline[maxn<<1]; int len[maxn<<2][4]; int cov[maxn<<2]; int x[maxn]; int z[maxn]; int cntx,cntz,n; void init() { cntx=cntz=0; } void pushup(int num,int s,int e) { if(cov[num]>=3) { len[num][3]=len[num][0]; len[num][1]=len[num][2]=0; } else if(cov[num]==2) { if(s==e) { len[num][1]=len[num][3]=0; len[num][2]=len[num][0]; } else { len[num][3]=len[num<<1][3]+len[num<<1|1][3]+len[num<<1][2]+len[num<<1|1][2] +len[num<<1][1]+len[num<<1|1][1]; len[num][2]=len[num][0]-len[num][3]; len[num][1]=0; } } else if(cov[num]==1) { if(s==e) { len[num][1]=len[num][0]; len[num][2]=len[num][3]=0; } else { len[num][3]=len[num<<1][3]+len[num<<1|1][3]+len[num<<1][2]+len[num<<1|1][2]; len[num][2]=len[num<<1][1]+len[num<<1|1][1]; len[num][1]=len[num][0]-len[num][2]-len[num][3]; } } else { len[num][3]=len[num<<1][3]+len[num<<1|1][3]; len[num][2]=len[num<<1][2]+len[num<<1|1][2]; len[num][1]=len[num<<1][1]+len[num<<1|1][1]; } } void build(int num,int s,int e) { len[num][0]=x[e+1]-x[s]; len[num][1]=len[num][2]=len[num][3]=0; cov[num]=0; if(s==e)return; int mid=(s+e)>>1; build(lson); build(rson); } void update(int num,int s,int e,int l,int r,int val) { if(l<=s && r>=e) { cov[num]+=val; if(cov[num]>=3) { len[num][3]=len[num][0]; len[num][1]=len[num][2]=0; } else if(cov[num]==2) { if(s==e) { len[num][1]=len[num][3]=0; len[num][2]=len[num][0]; } else { len[num][3]=len[num<<1][3]+len[num<<1|1][3]+len[num<<1][2]+len[num<<1|1][2] +len[num<<1][1]+len[num<<1|1][1]; len[num][2]=len[num][0]-len[num][3]; len[num][1]=0; } } else if(cov[num]==1) { if(s==e) { len[num][1]=len[num][0]; len[num][2]=len[num][3]=0; } else { len[num][3]=len[num<<1][3]+len[num<<1|1][3]+len[num<<1][2]+len[num<<1|1][2]; len[num][2]=len[num<<1][1]+len[num<<1|1][1]; len[num][1]=len[num][0]-len[num][2]-len[num][3]; } } else { len[num][3]=len[num<<1][3]+len[num<<1|1][3]; len[num][2]=len[num<<1][2]+len[num<<1|1][2]; len[num][1]=len[num<<1][1]+len[num<<1|1][1]; } return ; } int mid=(s+e)>>1; if(l<=mid)update(lson,l,r,val); if(r>mid)update(rson,l,r,val); pushup(num,s,e); } void solve(int kase) { build(1,0,cntx-2); LL ans=0; for(int i=0;i<cntz-1;i++) { int cnt=0; for(int j=0;j<n;j++) { if(cube[j].z1<=z[i] && cube[j].z2>z[i]) { scline[cnt].s=cube[j].x1; scline[cnt].e=cube[j].x2; scline[cnt].h=cube[j].y1; scline[cnt++].type=1; scline[cnt].s=cube[j].x1; scline[cnt].e=cube[j].x2; scline[cnt].h=cube[j].y2; scline[cnt++].type=-1; } } LL area=0; sort(scline,scline+cnt); for(int j=0;j<cnt-1;j++) { int l=lower_bound(x,x+cntx,scline[j].s)-x; int r=lower_bound(x,x+cntx,scline[j].e)-x; update(1,0,cntx-2,l,r-1,scline[j].type); area+=(LL)len[1][3]*(scline[j+1].h-scline[j].h); } int l=lower_bound(x,x+cntx,scline[cnt-1].s)-x; int r=lower_bound(x,x+cntx,scline[cnt-1].e)-x; update(1,0,cntx-2,l,r-1,scline[cnt-1].type); ans+=area*(z[i+1]-z[i]); } printf("Case %d: %I64d\n",kase,ans); } int main() { int T; scanf("%d",&T); for(int cas=1;cas<=T;cas++) { init(); scanf("%d",&n); for(int i=0;i<n;i++) { cube[i].scan(); x[cntx++]=cube[i].x1; x[cntx++]=cube[i].x2; z[cntz++]=cube[i].z1; z[cntz++]=cube[i].z2; } sort(x,x+cntx); sort(z,z+cntz); cntx=unique(x,x+cntx)-x; cntz=unique(z,z+cntz)-z; solve(cas); } return 0; }
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115678.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...