https://www.luogu.org/problem/show?pid=2745
本來因為會WA的，結果AC了，啊哈哈哈哈哈哈哈哈哈
因為題目要求我們要把一個個平面有先后關系，那么我們就搞一個隊列嘛，每次詢問時，不斷把平面上升就好了；
但是一個平面被另一個平面擋住一部分，剩下的可以簡單得理解為4個部分：
上下左右
111122
111122
440022
440022
443333
443333
如圖，大矩形被小矩形（以0表示），可以分為1 2 3 4 個部分；
我給大家一個正確的程序
表示矩形A左上角(x1,y1)右下角(x2,y2)被矩形B（xy同理）遮擋后的面積；

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #define Ll long long using namespace std; int ans,x1,y1,x2,y2,x3,y3,x4,y4,xx,yy,xxx,yyy; void pd(int x,int y,int xx,int yy){if(x==xx||y==yy)return;ans+=(xx-x)*(yy-y); } int main() {cin>>x1>>y1>>x2>>y2;cin>>x3>>y3>>x4>>y4;if(x3>=x2||y3>=y2||x4<=x1||y4<=y1){ans+=(x2-x1)*(y2-y1);}elseif(x1>=x3&&x2<=x4&&y1>=y3&&y2<=y4){ans=0;}else{pd(x1,y1,max(x3,x1),min(y4,y2));pd(x1,min(y2,y4),min(x2,x4),y2);pd(min(x2,x4),max(y1,y3),x2,y2);pd(max(x3,x1),y1,x2,max(y1,y3));}cout<<ans; }

AC代碼

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<map> #define Ll long long using namespace std; map<char,int>F; int a[1000][4]; string s; char c; int ll,k,lll,ans; void dfs(int x1,int y1,int x2,int y2,int k){//printf("%d %d %d %d %d\n",x1,y1,x2,y2,k);if(x1==x2||y1==y2)return;if(k>ll){ans+=(x2-x1)*(y2-y1);return;}int x3=a[k][0],y3=a[k][1],x4=a[k][2],y4=a[k][3];if(x3>=x2||y3>=y2||x4<=x1||y4<=y1){dfs(x1,y1,x2,y2,k+1);return;}if(x1>=x3&&x2<=x4&&y1>=y3&&y2<=y4)return;dfs(x1,y1,max(x3,x1),min(y4,y2),k+1);dfs(x1,min(y2,y4),min(x2,x4),y2,k+1);dfs(min(x2,x4),max(y1,y3),x2,y2,k+1);dfs(max(x3,x1),y1,x2,max(y1,y3),k+1); } int main(){ll=100;lll=101;while(cin>>s){c=s[2];if(s[0]=='w'){ll++;F[c]=ll;k=4;for(int i=0;i<=3;i++){while(isdigit(s[k])){a[ll][i]=a[ll][i]*10+s[k]-48;k++;}k++;}int x=a[ll][0],y=a[ll][1],xx=a[ll][2],yy=a[ll][3];a[ll][0]=min(x,xx);a[ll][1]=min(y,yy);a[ll][2]=max(x,xx);a[ll][3]=max(y,yy);}elseif(s[0]=='t'){k=F[c];ll++;for(int i=0;i<=3;i++)a[ll][i]=a[k][i],a[k][i]=1e8;F[c]=ll;}elseif(s[0]=='b'){k=F[c];lll--;for(int i=0;i<=3;i++)a[lll][i]=a[k][i],a[k][i]=1e8;F[c]=lll;}elseif(s[0]=='d'){k=F[c];for(int i=0;i<=3;i++)a[k][i]=1e8;F[c]=0;}else{ans=0;k=F[c];dfs(a[k][0],a[k][1],a[k][2],a[k][3],k+1);k=(a[k][2]-a[k][0])*(a[k][3]-a[k][1]);double kill=double(ans)/double(k);kill*=double(100);printf("%.3lf\n",kill);}} }

轉載于:https://www.cnblogs.com/largecube233/p/6797963.html

總結

以上是生活随笔為你收集整理的拆分-洛谷P2745 [USACO5.3]窗体面积Window Area的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。