用一个表保存矩阵的先后顺序，w,t,b,d都对表进行操作，同时维护一个hash表查找标识符对应的下标。
s时，采用上浮法得到矩阵面积。
/**//*
ID: lorelei3
TASK: window
LANG: C++
*/
#include <fstream>
#include <iostream>
using namespace std;
const int MAX = 20000;
struct Rect
{
char mark;
int lx, ly, rx, ry;
};
int cnt;
Rect rect[MAX];
int hash[300];
void create(char mark, int x1, int y1, int x2, int y2){
cnt++;
hash[mark]=cnt;
rect[cnt].mark = mark;
rect[cnt].lx=x1, rect[cnt].ly=y1, rect[cnt].rx=x2, rect[cnt].ry=y2;
}
void top(char mark){
int i = hash[mark];
Rect tmp = rect[i];
while(i<cnt){
rect[i] = rect[i+1];
hash[rect[i].mark]--;
i++;
}
rect[cnt]=tmp;
hash[mark]=cnt;
}
void bottom(char mark){
int i = hash[mark];
Rect tmp = rect[i];
while(i>1){
rect[i] = rect[i-1];
hash[rect[i].mark]++;
i--;
}
rect[1]=tmp;
hash[mark]=1;
}
void del(char mark){
int i = hash[mark];
while(i<cnt){
rect[i]=rect[i+1];
hash[rect[i].mark]--;
i++;
}
cnt--;
}
double cover(int lx, int ly, int rx, int ry, int k){
while(k<=cnt&&( lx >= rect[k].rx ||
rx <= rect[k].lx ||
ly >= rect[k].ry ||
ry <= rect[k].ly ))
k++;
double sum=0;
if(k>cnt){ return (ry-ly) * (rx-lx); }
if(lx<rect[k].lx) { sum+=cover(lx, ly, rect[k].lx, ry, k+1); lx=rect[k].lx; }
if(rx>rect[k].rx) { sum+=cover(rect[k].rx, ly, rx, ry, k+1); rx=rect[k].rx; }
if(ly<rect[k].ly) { sum+=cover(lx, ly, rx, rect[k].ly, k+1); ly=rect[k].ly; }
if(ry>rect[k].ry) { sum+=cover(lx, rect[k].ry, rx, ry, k+1); ry=rect[k].ry; }
return sum;
}
double show(char mark){
int i = hash[mark];
double res = cover(rect[i].lx, rect[i].ly, rect[i].rx, rect[i].ry, i+1 );
return 100*(res/((rect[i].ry-rect[i].ly)*(rect[i].rx-rect[i].lx)));
}
inline int min(int a, int b){
return a<b?a:b;
}
inline int max(int a, int b){
return a>b?a:b;
}
int main(){
int x1,y1,x2,y2;
char op, mark, ch;
ifstream fin("window.in");
ofstream fout("window.out");
fout.setf(ios::fixed);
fout.precision(3);
while((op=(char)fin.get())!=EOF){
if(op=='w'){
fin>>ch>>mark>>ch>>x1>>ch>>y1>>ch>>x2>>ch>>y2>>ch;
int lx=min(x1,x2), ly=min(y1,y2), rx=max(x1,x2), ry=max(y1,y2);
create(mark, lx, ly, rx, ry);
}else if(op=='t'){
fin>>ch>>mark>>ch;
top(mark);
}else if(op=='b'){
fin>>ch>>mark>>ch;
bottom(mark);
}else if(op=='d'){
fin>>ch>>mark>>ch;
del(mark);
}else if(op=='s'){
fin>>ch>>mark>>ch;
double res = show(mark);
fout<<res<<endl;
}
fin.get();
}
return 0;
}
posted on 2011-02-10 23:14
小阮 阅读(307)
评论(0) 编辑 收藏 引用 所属分类:
USACO