Usaco Training Section 5.3 Window Area

有一堆窗户，以及一些创建、置顶、置地、删除的操作，中间要询问几次某个窗户可见的百分比是多少。

对于创建、置顶、置地、删除的操作，直接模拟即可。主要是询问。

求可见百分比，要求出可见范围，也就是求被覆盖的面积，这是经典的矩阵覆盖。可用扫描线来实现。

懒得写线段树（貌似也并不需要），直接排序+推一推。

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define inf 2147483647
#define mp make_pair
#define pii pair<int,int>
#define pb push_back
#define r1 rt<<1
#define r2 rt<<1|1
#define ld long double
using namespace std;

inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}

struct node{
	int x1,y1,x2,y2;
}b[200],a[200];
struct node2{
	int l,r;
}d[200];
vector<int> v;
int c[200];

inline bool cmp(node2 x,node2 y){
	if(x.l!=y.l) return x.l<y.l;
	else return x.r<y.r;
}

int main()
{
	ios::sync_with_stdio(false);
	freopen("window.in","r",stdin);
	freopen("window.out","w",stdout);
	string s;
	while(cin>>s){
		if(s[0]=='w'){
			int i=s[2];
			int p=4,y1=0,x1=0,x2=0,y2=0;
			while(s[p]!=',') x1=(x1<<1)+(x1<<3)+(s[p]^48),++p;++p;
			while(s[p]!=',') y1=(y1<<1)+(y1<<3)+(s[p]^48),++p;++p;
			while(s[p]!=',') x2=(x2<<1)+(x2<<3)+(s[p]^48),++p;++p;
			while(s[p]!=')') y2=(y2<<1)+(y2<<3)+(s[p]^48),++p;
			a[i].x1=min(x1,x2),a[i].y1=min(y1,y2),a[i].x2=max(x1,x2),a[i].y2=max(y1,y2);
			v.pb(i);
		}
		else if(s[0]=='t'){
			int i=s[2],j;
			for(j=0;j<v.size();++j)
				if(v[j]==i) break;
			v.erase(v.begin()+j);
			v.pb(i);
		}
		else if(s[0]=='b'){
			int i=s[2],j;
			for(j=0;j<v.size();++j)
				if(v[j]==i) break;
			v.erase(v.begin()+j);
			v.insert(v.begin(),i);
		}
		else if(s[0]=='d'){
			int i=s[2],j;
			for(j=0;j<v.size();++j)
				if(v[j]==i) break;
			v.erase(v.begin()+j);
		}
		else{
			int x=s[2],p;
			for(p=0;p<v.size();++p)
				if(v[p]==x) break;
			int tot=0,cnt=0;
			for(int i=p+1;i<v.size();++i){
				b[++tot].x1=max(a[x].x1,a[v[i]].x1);
				b[tot].y1=max(a[x].y1,a[v[i]].y1);
				b[tot].x2=min(a[x].x2,a[v[i]].x2);
				b[tot].y2=min(a[x].y2,a[v[i]].y2);
				if(b[tot].x1>b[tot].x2||b[tot].y1>b[tot].y2) --tot;
				else c[++cnt]=b[tot].x1,c[++cnt]=b[tot].x2;
			}
			if(tot==0){
				cout<<"100.000"<<endl;
				continue;
			}
			sort(c+1,c+cnt+1);
			int pos=1;
			ld ans=0;
			for(int i=1;i<cnt;++i){
				int sum=0;
				for(int j=1;j<=tot;++j)
					if(b[j].x1<=c[i]&&c[i+1]<=b[j].x2)d[++sum].l=b[j].y1,d[sum].r=b[j].y2;
				sort(d+1,d+sum+1,cmp);
				ld le=0;int j;
				for(j=1;j<=sum;++j){
					int st=d[j].l,en=d[j].r;
					while(j+1<=sum&&en>=d[j+1].l){
						++j;
						en=max(en,d[j].r);
					}
					le+=en-st;
				}
				ans+=le*(ld)(c[i+1]-c[i]);
			}
			ld area=(ld)(a[x].x2-a[x].x1)*(ld)(a[x].y2-a[x].y1);
			ld y=(area-ans)/area;
			y*=100;
			cout<<setiosflags(ios::fixed)<<setprecision(3)<<y<<endl;
		}
	}
	return 0; 
}