https://www.luogu.org/problemnew/show/P2745
上浮法...真是奇特的方法
考虑到我们要把矩形置顶，那么如果我们置顶到第k层，现在摆在我们面前的是第k层的矩形
将矩形分为四个继续上浮即可
#include<cstdio> #include<iostream> #include<cstring> #include<queue> #include<vector> #include<map> #include<climits> #include<algorithm> using namespace std; typedef long long ll; typedef double db; #define pii pair<ll,int> #define mp make_pair #define B cout << "breakpoint" << endl; #define O(x) cout << #x << " " << x << endl; inline int read() { int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { (ans *= 10) += ch - '0'; ch = getchar(); } return ans * op; } db ans,base; const int maxn = 1005; struct node { int x1,y1,x2,y2; char id; void init() { x1 = y1 = x2 = y2 = 0; id = 0; } bool operator == (const node& b) const { return id == b.id; } }a[maxn],tp[maxn]; bool vis[maxn]; int n; inline int find(node x) { for(int i = 1;i <= n;i++) if(a[i] == x) return i; } void move(node x,int f) { int pos = find(x); if(f == 0) for(int i = pos;i >= 2;i--) swap(a[i],a[i - 1]); else for(int i = pos;i < n;i++) swap(a[i],a[i + 1]); } void del(node x) { int pos = find(x); tp[x.id] = (node){0,0,0,0,0}; vis[x.id] = 0; for(int i = pos + 1;i <= n;i++) a[i - 1] = a[i]; n--; } void dfs(int k,int x1,int y1,int x2,int y2) { if(x1 == x2 || y1 == y2) return; if(k == 0) { ans += (db)(x2 - x1) * (y2 - y1); return; } int a1 = a[k].x1,b1 = a[k].y1,a2 = a[k].x2,b2 = a[k].y2; if(x1 > a2 || x2 < a1 || y1 > b2 || y2 < b1) { dfs(k - 1,x1,y1,x2,y2); return; } if(a1 <= x1 && a2 >= x2 && b1 <= y1 && b2 >= y2) return; dfs(k - 1,x1,min(y2,b2),min(x2,a2),y2); dfs(k - 1,min(a2,x2),max(y1,b1),x2,y2); dfs(k - 1,max(x1,a1),y1,x2,max(y1,b1)); dfs(k - 1,x1,y1,max(x1,a1),min(y2,b2)); } int main() { char op; int x1,y1,x2,y2; char id; node tpt; while(cin >> op) { if(op == 's') { scanf("(%c",&id); int pos = 0; for(int i = 1;i <= n;i++) if(a[i] == tp[id]) pos = i; ans = 0,base = (db)(a[pos].x2 - a[pos].x1) * (a[pos].y2 - a[pos].y1); dfs(pos - 1,a[pos].x1,a[pos].y1,a[pos].x2,a[pos].y2); printf("%.3lf ",ans * 100 / base); } else { scanf("(%c,%d,%d,%d,%d)", &id, &x1, &y1, &x2, &y2); if(x1 > x2) swap(x1, x2); if(y1 > y2) swap(y1, y2); tpt = (node){x1,y1,x2,y2,id}; if(op == 'w') { if(vis[id]) continue; tp[id] = a[++n] = tpt,move(tpt,0),vis[id] = 1; } if(op == 't') move(tpt, 0); if(op == 'b') move(tpt, 1); if(op == 'd') del(tpt); } } }