本文共 3060 字，大约阅读时间需要 10 分钟。
题意：给你一些长方体，问你覆盖三次及以上的体积有多大
首先我们观察x轴y轴一样很大，但是z轴很小，所以我们可以枚举z轴（-500,500）,注意我们枚举的是每一段长度为一的z轴的xy轴的面积而不是点。接着就是求在这一段内的矩形面积并的变形
注意我们要首先计算，再插入线段求面积并
#include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define eps 1E-8/*注意可能会有输出-0.000*/#define Sgn(x) (x<-eps? -1 :x 0.0 ? x+eps : x-eps)//浮点数转化#define zero(x) (((x)>0?(x):-(x)) >b)typedef long long ll;typedef unsigned long long ull;const int Inf=1<<28;const double Pi=acos(-1.0);const int Mod=1e9+7;const int Max=1010;struct node{ int xx1,yy1,zz1,xx2,yy2,zz2;} rec [Max];struct nude{ int xx1,xx2,yy1,cover;} lin[Max<<1];struct nide{ int cover,dp[4];//覆盖次数 此点代表值} segtr[Max<<3];map mp;int mpx[Max<<1];void Upnow(int now,int next){ segtr[now].dp[0]=segtr[next].dp[0]+segtr[next|1].dp[0]; return;}void Create(int sta,int enn,int now){ segtr[now].dp[1]=segtr[now].dp[2]=segtr[now].dp[3]=0; segtr[now].cover=0; if(sta==enn) { segtr[now].dp[0]=mpx[sta+1]-mpx[sta]; return; } int mid=dir(sta+enn,1); int next=mul(now,1); Create(sta,mid,next); Create(mid+1,enn,next|1); Upnow(now,next); return;}void Jud(int sta,int enn,int now){ int next=mul(now,1); if(segtr[now].cover>=3) { segtr[now].dp[3]=segtr[now].dp[0]; segtr[now].dp[1]=segtr[now].dp[2]=0; } else if(segtr[now].cover==2) { segtr[now].dp[1]=0; if(sta==enn) { segtr[now].dp[3]=0; } else { segtr[now].dp[3]=segtr[next].dp[1]+segtr[next|1].dp[1]+segtr[next].dp[2]+segtr[next|1].dp[2]+segtr[next].dp[3]+segtr[next|1].dp[3]; } segtr[now].dp[2]=segtr[now].dp[0]-segtr[now].dp[3]; } else if(segtr[now].cover==1) { if(sta==enn) { segtr[now].dp[2]=segtr[now].dp[3]=0; segtr[now].dp[1]=segtr[now].dp[0]; } else { segtr[now].dp[2]=segtr[next].dp[1]+segtr[next|1].dp[1]; segtr[now].dp[3]=segtr[next].dp[2]+segtr[next|1].dp[2]+segtr[next].dp[3]+segtr[next|1].dp[3]; segtr[now].dp[1]=segtr[now].dp[0]-segtr[now].dp[3]-segtr[now].dp[2]; } } else { if(sta==enn) { segtr[now].dp[1]=segtr[now].dp[2]=segtr[now].dp[3]=0; } else { segtr[now].dp[1]=segtr[next].dp[1]+segtr[next|1].dp[1]; segtr[now].dp[2]=segtr[next].dp[2]+segtr[next|1].dp[2]; segtr[now].dp[3]=segtr[next].dp[3]+segtr[next|1].dp[3]; } } return;}void Update(int sta,int enn,int now,int x,int y,int z){ if(x<=sta&&enn<=y) { segtr[now].cover+=z; Jud(sta,enn,now); return; } int mid=dir(sta+enn,1); int next=mul(now,1); if(mid>=x) Update(sta,mid,next,x,y,z); if(mid p2.cover; return p1.yy1 i)//段变点 { mp[rec[j].xx1]=1; mp[rec[j].xx2]=1; lin[coun].xx1=rec[j].xx1,lin[coun].xx2=rec[j].xx2,lin[coun].yy1=rec[j].yy1,lin[coun++].cover=1; lin[coun].xx1=rec[j].xx1,lin[coun].xx2=rec[j].xx2,lin[coun].yy1=rec[j].yy2,lin[coun++].cover=-1; } } int cnt=0; for(map ::iterator it=mp.begin(); it!=mp.end(); ++it) { it->second=++cnt;//离散化 mpx[cnt]=it->first; } mpx[cnt+1]=mpx[cnt]; sum+=Vol(n,cnt,coun); } return sum;}int main(){ int t,n,coun=0; scanf("%d",&t); while(t--) { scanf("%d",&n); for(int i=0; i
转载于:https://www.cnblogs.com/zhuanzhuruyi/p/5914718.html