Window Area_usaco 5.3

NO IMAGE
1 Star2 Stars3 Stars4 Stars5 Stars 給文章打分!
Loading...

Description


你剛剛接手一項窗體介面工程。窗體介面還算簡單,而且幸運的是,你不必顯示實際的窗體。有 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 的範圍內。

Input


輸入檔案包含給你的解釋程式的一系列命令,每行一個。當輸入檔案結束時,停止程式。

Output


只對於 s() 命令進行輸出。當然,輸入檔案可能有許多 s() 命令(不超過500次),所以輸出檔案應該是一個百分比的序列,每行一個,百分比是窗體可見部分的百分比。百分比應該四捨五入到三位小數。

Analysis


一種新的方法,學習一下
對於視窗我們開一個佇列,每次置頂或置底就放在隊頭和隊尾,對於所有的查詢我們用dfs做
每次讓指定的矩形上浮,遇到位於上方且相交的矩形就破碎分割成小矩形繼續上浮,最後統計剩下的面積

Code


/*
ID:wjp13241
PROG:window
LANG:C  
*/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <stack>
#include <queue>
#define fo(i,a,b) for (int i=a;i<=b;i  )
#define dfo(i,a,b) for (int i=a;i>=b;i--)
#define fil(x,t) memset(x,t,sizeof(x))
#define STP system("pause")
#define min(x,y) x<y?x:y
#define max(x,y) x>y?x:y
#define ld long double
#define ll long long
#define INF 0x3f3f3f3f
#define EPS 1e-4
#define N 201
#define E N*N 1
using namespace std;
struct window{int u,d,l,r;char n;}p[E];
int area=0;
void swap(window &a,window &b){window tmp=a;a=b;b=tmp;}
void cal(int now,int u,int d,int l,int r,int cnt)
{
while (now<=cnt&&(p[now].d<=u||p[now].u>=d||p[now].l>=r||p[now].r<=l))
now  ;
if (now>cnt)
{
area =(d-u)*(r-l);
return;
}
if (p[now].u>u)
{
cal(now 1,u,p[now].u,l,r,cnt);
u=p[now].u;
}
if (p[now].d<d)
{
cal(now 1,p[now].d,d,l,r,cnt);
d=p[now].d;
}
if (p[now].l>l)
{
cal(now 1,u,d,l,p[now].l,cnt);
l=p[now].l;
}
if (p[now].r<r)
{
cal(now 1,u,d,p[now].r,r,cnt);
r=p[now].r;
}
}
int main()
{
char opt;
int cnt=0;
while (~scanf("%c",&opt))
{
if (opt=='w')
{
int a,b,c,d;
char n;
scanf("%*c%c%*c%d%*c%d%*c%d%*c%d%*c",&n,&a,&b,&c,&d);
p[  cnt]=(window){min(a,c),max(a,c),min(b,d),max(b,d),n};
}
if (opt=='t')
{
char n;
scanf("%*c%c%*c",&n);
fo(i,1,cnt)
if (p[i].n==n)
{
fo(j,i 1,cnt)
swap(p[j],p[j-1]);
break;
}
}
if (opt=='b')
{
char n;
scanf("%*c%c%*c",&n);
dfo(i,cnt,1)
if (p[i].n==n)
{
dfo(j,i-1,1)
swap(p[j],p[j 1]);
break;
}
}
if (opt=='d')
{
char n;
scanf("%*c%c%*c",&n);
fo(i,1,cnt)
if (p[i].n==n)
{
fo(j,i 1,cnt)
swap(p[j],p[j-1]);
cnt--;
}
}
if (opt=='s')
{
char n;
scanf("%*c%c%*c",&n);
double ans=0;
area=0;
fo(i,1,cnt)
if (p[i].n==n)
{
cal(i 1,p[i].u,p[i].d,p[i].l,p[i].r,cnt);
ans=area/(1.0*(p[i].d-p[i].u)*(p[i].r-p[i].l))*100.0;
break;
}
printf("%.3f\n",ans);
}
getchar();
}
return 0;
}

相關文章

程式語言 最新文章