这个题 就是个工程题 （然而一开始我并不知道怎么做。。还是看nocow的。。qwq）（原题入口）
算法为 离散化 + 扫描线 将大坐标变小 并且 用横纵坐标进行扫描 来计算面积
一开始 我想边添加 点的坐标 边 离散 后来发现 有点问题
因为 它离散后的坐标 并不是按顺序来排（因为后来可能还加入中间的点 就需要重新离散）
所以 我就把一开始的操作 和 坐标先存下来 进行离散 再进行操作 （QAQ 搞了好久）
后面 就是计算面积了 把一个大矩形 划分成 许多个小矩形 再进行标记 来计算面积了
代码:
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cctype>
#include <iostream>
#include <map>
#include <vector>
#define For(i, l, r) for(int i = (l); i <= (int)(r); ++i)
#define Fordown(i, r, l) for(int i = (r); i >= (int)(l); --i)
#define Set(a, v) memset(a, v, sizeof(a))
#define pb push_back
using namespace std; inline int read(){
int x = , fh = ; char ch;
for(; !isdigit(ch); ch = getchar()) if (ch == '-') fh = -;
for(; isdigit(ch); ch = getchar()) x = (x<<) + (x<<) + (ch^'');
return x * fh;
} const int N = ;
map <int, int> fx, fy; //map数组 记录这个坐标是否被离散化过
int gx[<<], gy[<<]; //反向存储标号对应的坐标
int cnt_x = , cnt_y = , cnt = ; //离散化的个数
char id[N]; //记录id数组 int now_deep = *(<<), top_deep = (<<), back_deep = *(<<);
struct node {
int xl, yl, xr, yr;
int deep; //层次
bool flag; //是否被删除
};
node win[N]; //存储窗户 int idx(char ch) {
For (i, , cnt)
if (id[i] == ch) return i;
id[++cnt] = ch;
return cnt;
} //计算当前l的id bool exist[N/][N/];
double sum(int num) {
if (!win[num].flag) return 0.0000; //如果已经删除 就返回0.0 (好像并没有用)
Set(exist, false); //判断小矩形是否存在
int sum_area = ;
int now_area = ; For (i, win[num].xl, win[num].xr-)
For (j, win[num].yl, win[num].yr-)
{ exist[i][j] = true; //一开始置为真
sum_area += fabs ((gx[i+] - gx[i] ) * (gy[j+] - gy[j]) ) ; } //计算本来的总面积 For (i, , cnt)
if (win[i].flag && win[i].deep < win[num].deep) //如果在它上面 并且 未被删除
For (j, win[i].xl, win[i].xr-)
For (k, win[i].yl, win[i].yr-)
exist[j][k] = false; //小矩形置为假 For (i, win[num].xl, win[num].xr-)
For (j, win[num].yl, win[num].yr-)
if (exist[i][j]) //存在 就加上
now_area += fabs( (gx[i] - gx[i+]) * (gy[j] - gy[j+]) ); //计算面积 return ((double)now_area / (double)sum_area * 100.0000); //计算百分比
} struct oper {
char opt;
int l, xl, yl, xr, yr;
}; oper kk[N]; //存储操作
int cnt_op = ;
vector <int> tx; //存储坐标
vector <int> ty; int main(){
freopen ("window.in", "r", stdin);
freopen ("window.out", "w", stdout);
char opt;
while (scanf ("%c", &opt) != EOF) {
char l;
int xl1, yl1, xr1, yr1;
if (opt == 'w') {
scanf ("(%c,%d,%d,%d,%d)", &l, &xl1, &yl1, &xr1, &yr1);
if (xl1 > xr1) swap(xl1, xr1);
if (yl1 > yr1) swap(yl1, yr1); //左下角 和 右上角
kk[++cnt_op] = (oper) {opt, l, xl1, yl1, xr1, yr1};
tx.pb (xl1); tx.pb(xr1); ty.pb(yl1); ty.pb(yr1);
}
else {
scanf ("(%c)", &l);
kk[++cnt_op] = (oper) {opt, l, , , , };
}
} sort (tx.begin(), tx.end() );
For (i, , tx.size() - )
if (!fx[tx[i]] ) {fx[tx[i]] = ++cnt_x; gx[cnt_x] = tx[i]; }
sort (ty.begin(), ty.end() );
For (i, , ty.size() - )
if (!fy[ty[i]] ) {fy[ty[i]] = ++cnt_y; gy[cnt_y] = ty[i]; }
//运用map的离散化 可能有点慢 For (i, , cnt_op) {
//cout << "id: " << i << endl;
opt = kk[i].opt;
char l = kk[i].l; int num;
int xl1 = kk[i].xl, yl1 = kk[i].yl, xr1 = kk[i].xr, yr1 = kk[i].yr;
if (opt == 'w') {
num = idx(l);
win[num].xl = fx[xl1]; win[num].xr = fx[xr1];
win[num].yl = fy[yl1]; win[num].yr = fy[yr1];
win[num].flag = true; win[num].deep = --top_deep; //放在最上面 并将flag为真
} //创建一个新窗体(window)
else if (opt == 't') {
num = idx(l);
win[num].deep = --top_deep;
}//将窗体置顶(top)
else if (opt == 'b') {
num = idx(l);
win[num].deep = ++back_deep;
}//将窗体置底(back)
else if (opt == 'd') {
num = idx(l);
win[num].flag = false;
// cout << num << endl;
}//删除一个窗体(delete)
else if (opt == 's') {
num = idx(l);
printf ("%.3lf\n", sum(num));
}//输出窗体可见部分的百分比(sum)
}
}
