USACO Section 5.3 Window Area - 又一矩形覆盖问题

网友投稿 265 2022-08-25

USACO Section 5.3 Window Area - 又一矩形覆盖问题

最重要的问题..如何确定这些矩形的重叠层次顺序...我通过给每个矩形一个权值来表示当前矩形的优先级..只有当这个矩形某区域上有重合部分的矩形优先级都比这个矩形低..这个区域才说是从正面可以看到的面积...而这个优先级的操作:

用maxn表示当前优先级的最大值...用minn表示当前优先级的最小值..maxn与minn的初始值都为0..

当输入一个矩形..按题目的要求其优先值就应该比前面已经在那得所有矩形都高..所以他的优先级为maxn+1..且maxn随后++...

当要将一个矩形置顶时..同样..将这个矩形的优先级更新为maxn+1..且maxn随后++...

当要将一个矩形置底时..那么将这个矩形的优先值设定为比其他所有的优先级都低..所以为minn-1...且随后minn--..

当要删除一个矩形..我是直接标记为这个举行不存在..因为题目所给的所有矩形的点都是正整数..所以我标记为matrix[i].x0=0..

做好这些操作..那么就是在第三章写过的通过递归求矩形覆盖问题的面积了...很简单...

Program:

/* ID: zzyzzy12 LANG: C++ TASK: window*/ #include #include #include #include #include #include#include#include #include #define oo 2000000005 #define ll long long #define pi (atan(2)+atan(0.5))*2 using namespace std;struct node{ int x0,y0,x1,y1,t; }matrix[75];char c;int k,p,maxn,minn,m;double ans; void getdata(int i,int x0,int y0,int x1,int y1){ if (x0>=x1 || y0>=y1) return; for (;i<=75;i++) if (matrix[i].x0 && matrix[i].t>matrix[k].t) break; if (i==76) { m+=(x1-x0)*(y1-y0); return; } getdata(i+1,x0,y0,min(x1,matrix[i].x0),y1); getdata(i+1,max(x0,matrix[i].x1),y0,x1,y1); getdata(i+1,max(x0,matrix[i].x0),max(y0,matrix[i].y1),min(x1,matrix[i].x1),y1); getdata(i+1,max(x0,matrix[i].x0),y0,min(x1,matrix[i].x1),min(y1,matrix[i].y0)); return; }int main() { freopen("window.in","r",stdin); freopen("window.out","w",stdout); memset(matrix,0,sizeof(matrix)); maxn=minn=0; while (~scanf("%c",&c)) { if (c=='w') { scanf("%c%c",&c,&c); if (c>='0' && c<='9') k=60+c-'0'; else if (c>='a') k=c-'a'+1; else k=c-'A'+27; scanf(",%d,%d,%d,%d",&matrix[k].x0,&matrix[k].y0,&matrix[k].x1,&matrix[k].y1); if (matrix[k].x0>matrix[k].x1) { p=matrix[k].x0; matrix[k].x0=matrix[k].x1; matrix[k].x1=p; } if (matrix[k].y0>matrix[k].y1) { p=matrix[k].y0; matrix[k].y0=matrix[k].y1; matrix[k].y1=p; } matrix[k].t=++maxn; }else if (c=='t') { scanf("%c%c",&c,&c); if (c>='0' && c<='9') k=60+c-'0'; else if (c>='a') k=c-'a'+1; else k=c-'A'+27; matrix[k].t=++maxn; }else if (c=='b') { scanf("%c%c",&c,&c); if (c>='0' && c<='9') k=60+c-'0'; else if (c>='a') k=c-'a'+1; else k=c-'A'+27; matrix[k].t=--minn; }else if (c=='d') { scanf("%c%c",&c,&c); if (c>='0' && c<='9') k=60+c-'0'; else if (c>='a') k=c-'a'+1; else k=c-'A'+27; matrix[k].x0=0; }else if (c=='s') { scanf("%c%c",&c,&c); if (c>='0' && c<='9') k=60+c-'0'; else if (c>='a') k=c-'a'+1; else k=c-'A'+27; ans=(matrix[k].x1-matrix[k].x0)*(matrix[k].y1-matrix[k].y0); m=0; getdata(1,matrix[k].x0,matrix[k].y0,matrix[k].x1,matrix[k].y1); ans=m/ans*100; printf("%.3lf\n",ans); } } return 0; }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。

标签：输入
上一篇:USACO Section 5.2 Wisconsin Squares - 按要求DFS就行了..
下一篇:2022年如何进行抖音营销呢？（抖音2020年销售额）
相关文章

 发表评论

暂时没有评论，来抢沙发吧~