记录编号	81789	评测结果	AAAAAAAAAAA
题目名称	窗体面积	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.023 s
提交时间	2013-11-17 22:17:13	内存使用	0.32 MiB

#include<iostream>
#include<cstdio>
#include<set>
#include<vector>
#include<cstring>
#include<deque>
#include<cstring>
#include<map>
#include<algorithm>
#include<iomanip>
using namespace std;
const int SIZEN=80;
const int n=62;
int charid(char ch){
	if('A'<=ch&&ch<='Z') return ch-'A';
	if('a'<=ch&&ch<='z') return ch-'a'+26;
	if('0'<=ch&&ch<='9') return ch-'0'+52;
	return -1;
}
class RECT{
public:
	bool exi;
	int minx,miny;
	int maxx,maxy;
	int dep;//最上面为0,向下递增
	int area(void){
		return (maxx-minx)*(maxy-miny);
	}
	void print(void){//调试接口,输出矩形信息
		cout<<minx<<" "<<miny<<" "<<maxx<<" "<<maxy<<endl;
	}
	RECT(){
		exi=false;
		minx=miny=maxx=maxy=0;
		dep=0;
	}
};
RECT r[SIZEN];//所有的窗体
vector<int> c[SIZEN];//储存'压了谁'
void outside(void){//调试接口,输出边的信息
	cout<<"===================="<<endl;
	cout<<"边的信息如下:"<<endl;
	for(int i=0;i<n;i++){
		if(!r[i].exi) continue;
		cout<<i<<" above:"<<endl;
		for(int j=0;j<c[i].size();j++){
			cout<<c[i][j]<<" ";
		}
		cout<<endl;
	}
	cout<<"===================="<<endl;
}
void outdep(void){//调试接口,输出深度信息
	cout<<"===================="<<endl;
	cout<<"深度信息如下:"<<endl;
	for(int i=0;i<n;i++){
		if(!r[i].exi) continue;
		cout<<i<<"深"<<r[i].dep<<endl;
	}
	cout<<"===================="<<endl;
}
void markdep(void){//拓扑排序
	int adeg[SIZEN]={0};//入边数
	int i,j;
	for(i=0;i<n;i++){
		if(!r[i].exi) continue;
		for(j=0;j<c[i].size();j++) adeg[c[i][j]]++;
	}
	int tot=0;
	vector<int> cl;
	bool flag;
	while(true){
		cl.clear();
		flag=false;
		for(i=0;i<n;i++){
			if(!r[i].exi) continue;
			if(adeg[i]==0){
				cl.push_back(i);
				flag=true;
			}
		}
		if(!flag) break;
		for(i=0;i<cl.size();i++){
			adeg[cl[i]]=-1;
			r[cl[i]].dep=tot;
			for(j=0;j<c[cl[i]].size();j++) adeg[c[cl[i]][j]]--;
		}
		tot++;
	}
}
bool intersectant(RECT &a,RECT &b){//二矩形是否相交
	if(a.minx>=b.maxx) return false;
	if(a.maxx<=b.minx) return false;
	if(a.miny>=b.maxy) return false;
	if(a.maxy<=b.miny) return false;
	return true;
}
int visiblearea(RECT now,int pos){//矩形now(是矩形r[pos]的一部分)的可见部分
	int i;
	RECT temp;
	int sum=0;
	bool kpd=false;
	for(i=0;i<n;i++){
		if(!r[i].exi) continue;
		if(i==pos) continue;
		if(r[i].dep>=now.dep) continue;
		if(!intersectant(now,r[i])) continue;
		kpd=true;
		if(r[i].maxy<now.maxy){
			temp=now;
			temp.miny=r[i].maxy;
			sum+=visiblearea(temp,pos);
			temp.maxy=r[i].maxy;
			temp.miny=now.miny;
			sum+=visiblearea(temp,pos);
			return sum;
		}
		if(r[i].miny>now.miny){
			temp=now;
			temp.maxy=r[i].miny;
			sum+=visiblearea(temp,pos);
			temp.maxy=now.maxy;
			temp.miny=r[i].miny;
			sum+=visiblearea(temp,pos);
			return sum;
		}
		if(r[i].maxx<now.maxx){
			temp=now;
			temp.minx=r[i].maxx;
			sum+=visiblearea(temp,pos);
			temp.maxx=r[i].maxx;
			temp.minx=now.minx;
			sum+=visiblearea(temp,pos);
			return sum;
		}
		if(r[i].minx>now.minx){
			temp=now;
			temp.maxx=r[i].minx;
			sum+=visiblearea(temp,pos);
			temp.maxx=now.maxx;
			temp.minx=r[i].minx;
			sum+=visiblearea(temp,pos);
			return sum;
		}
	}
	if(!kpd) return now.area();
	else return 0;
}
int visiblearea(int x){//矩形r[x]的可见部分
	return visiblearea(r[x],x);
}
void eraseside(int x){//擦除一切与点x有关的边
	int i,j;
	c[x].clear();
	for(i=0;i<n;i++){
		for(j=0;j<c[i].size();j++){
			if(c[i][j]==x) c[i].erase(c[i].begin()+j);
		}
	}
}
void placetop(int x){//将矩形r[x]置顶
	int i;
	eraseside(x);
	for(i=0;i<n;i++){
		if(!r[i].exi||i==x) continue;
		if(!intersectant(r[x],r[i])) continue;
		c[x].push_back(i);
	}
	markdep();
}
void placebottom(int x){//将矩形r[x]置底
	int i;
	eraseside(x);
	for(i=0;i<n;i++){
		if(!r[i].exi||i==x) continue;
		if(!intersectant(r[x],r[i])) continue;
		c[i].push_back(x);
	}
	markdep();
}
void creat(int x,int minx,int miny,int maxx,int maxy){//创建矩形,若已存在则重新创建
	r[x].exi=true;
	r[x].minx=minx,r[x].miny=miny;
	r[x].maxx=maxx,r[x].maxy=maxy;
	r[x].dep=0;
	placetop(x);
}
void erase(int x){//擦除矩形
	placebottom(x);
	r[x].exi=false;
	eraseside(x);
}
bool singlework(void){//处理一条命令
	char cmd;
	cin>>cmd;
	if(cin.eof()) return false;//经试验这种方法可以应对linux下的"文件结束"问题
	getchar();
	int minx,miny,maxx,maxy;
	char ID;
	int x1,x2,y1,y2;
	double s,s1;
	if(cmd=='w'){
		scanf("%c",&ID);
		getchar();
		scanf("%d",&x1);
		getchar();
		scanf("%d",&y1);
		getchar();
		scanf("%d",&x2);
		getchar();
		scanf("%d",&y2);
		minx=min(x1,x2),miny=min(y1,y2);
		maxx=max(x1,x2),maxy=max(y1,y2);
		creat(charid(ID),minx,miny,maxx,maxy);
	}
	else if(cmd=='t'){
		scanf("%c",&ID);
		placetop(charid(ID));
	}
	else if(cmd=='b'){
		scanf("%c",&ID);
		placebottom(charid(ID));
	}
	else if(cmd=='d'){
		scanf("%c",&ID);
		erase(charid(ID));
	}
	else if(cmd=='s'){
		scanf("%c",&ID);
		s1=visiblearea(charid(ID));
		s=r[charid(ID)].area();
		printf("%.3lf\n",s1/s*100);
	}
	getchar();
	getchar();
	if(cin.eof()) return false;
	return true;
}
int main(){
	freopen("windowus.in","r",stdin);
	freopen("windowus.out","w",stdout);
	while(singlework());
	return 0;
}