大概用的是最傻的方法...

Problem

你刚刚接手一项窗体界面工程。窗体界面还算简单，而且幸运的是，你不必显示实际的窗体。有 5 种基本操作：

创建一个新窗体

将窗体置顶

将窗体置底

删除一个窗体

输出窗体可见部分的百分比（就是，不被其它窗体覆盖的部分）。

在输入文件中，操作以如下的格式出现。

创建一个新窗体：w(I,x,y,X,Y)

将窗体置顶： t(I)

将窗体置底： b(I)

删除一个窗体：d(I)

输出窗体可见部分的百分比：s(I)

I 是每个窗体唯一的标识符，标识符可以是 'a'..'z', 'A'..'Z' 和 '0'..'9' 中的任何一个。输入文件中没有多余的空格。

（x,y）和（X,Y）是窗体的对角。当你创建一个窗体的时候，它自动被“置顶”。你不能用已经存在的标识符来创建窗体，但是你可以删除一个窗体后再用已删除窗体的标识符来创建窗体。坐标用正整数来表示，并且所有的窗体面积都不为 0（x <> X 且 y <> Y）。x 坐标和 y 坐标在 1 —— 32767 的范围内。

Solution

顺便补了一下扫描线是怎么求矩形面积并的（这里：https://www.cnblogs.com/KonjakJuruo/p/6024266.html ）

至于离散化... 就本题来说没必要 233

然后怎么模拟的话...

临时指定层数，然后每次询问看看哪些窗口比它大，算他们和该矩形的交，再算这些窗口的并

然后还有字符串的一些东西，这部分是乱搞的

这些东西加起来让我的代码变得很傻比

要注意窗口不相交 / 没有窗口与该窗口相交的一些情况。

Code

// Code by ajcxsu
// Problem: window area

#include<bits/stdc++.h>
using namespace std;

const int N=500;
struct Window {
    int x,y,X,Y,f; // floor
    bool u; // used
    void repair() {
        if(y>Y) swap(y,Y);
        if(x>X) swap(x,X);
    }
} wi[N];
int l=-1, r=0; // now floor

string aly(string x) {
    int itl=x.find('(')+1, itr=x.find(')')-1;
    x=x.substr(itl, itr-itl+1);
    return x;
}

const int M=40000;
#define ls x<<1
#define rs x<<1|1
int len[M*6], cnt[M*6];
void pup(int x, int d) {
    if(cnt[x]>0) len[x]=d;
    else len[x]=len[ls]+len[rs];
}
void updata(int x, int l, int r, int xl, int xr, int d) {
    if(l==xl && r==xr) { cnt[x]+=d; pup(x, r-l+1); return; }
    int mid=(l+r)>>1;
    if(xr<=mid) updata(ls, l, mid, xl, xr, d);
    else if(xl>mid) updata(rs, mid+1, r, xl, xr, d);
    else updata(ls, l, mid, xl, mid, d), updata(rs, mid+1, r, mid+1, xr, d);
    pup(x, r-l+1);
}

struct Seg{ int l, r, y, d; } se[N*2];
bool cmp(const Seg &a, const Seg &b) { return a.y<b.y; }
int np;
void check(char nd) {
    Window &n=wi[nd], m;
    double S=(n.Y-n.y)*(n.X-n.x);
    np=0;
    for(int i=0;i<N;i++) {
        if(!wi[i].u || wi[i].f<=n.f) continue;
        m=wi[i];
        m.x=max(m.x, n.x), m.y=max(m.y, n.y);
        m.X=min(m.X, n.X), m.Y=min(m.Y, n.Y);
        if(m.x>=m.X || m.y>=m.Y) continue;
        se[np++]={m.x, m.X, m.y, 1};
        se[np++]={m.x, m.X, m.Y, -1};
    }
    if(!np) { cout<<100.0<<endl; return; }
    sort(se, se+np, cmp);
    double NS=0, NL=0;
    updata(1,1,M-1,se[0].l,se[0].r-1,se[0].d);
    for(int i=1;i<np;i++) {
        NL=len[1];
        NS+=NL*(se[i].y-se[i-1].y);
        updata(1, 1, M-1, se[i].l, se[i].r-1, se[i].d);
    }
    cout<<(S-NS)*100.0/S<<endl;
}

int main() {
    ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout<<setprecision(3);
    string cmd, ana;
    while(cin>>cmd) {
        ana=aly(cmd);
        if(cmd[0]=='w') {
            int p=0;
            char a;
            int b[4];
            string x;
            while(ana[p]!=',') x+=ana[p++];
            a=x[0];
            for(int i=0;i<4;i++) {
                x="", p++;;
                while(p<ana.size() && ana[p]!=',') x+=ana[p++];
                b[i]=stoi(x);
            }
            wi[a].u=true;
            wi[a].x=b[0], wi[a].y=b[1], wi[a].X=b[2], wi[a].Y=b[3];
            wi[a].repair();
            wi[a].f=r++;
        }
        else {
            char a=ana[0];
            if(cmd[0]=='t') wi[a].f=r++;
            else if(cmd[0]=='b') wi[a].f=l--;
            else if(cmd[0]=='d') wi[a].u=false;
            else check(a);
        }
    }
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-luogu-2745.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆