ZOJ 2747 Paint the Wall(多矩形面积覆盖)
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2747
题意:
有n个矩形,每个矩形都有颜色,这些矩形相继被画到平板上去.问你最后平板上有哪些颜色,且各种颜色的面积各占多少? 颜色最多100种,用1-100标记.
分析:
本题类似于POJ 1151 :
http://blog.csdn.net/u013480600/article/details/39322791
本题首先离散化所有X和Y坐标,把平板分成小网格.然后用mp[i][j]数组标记小网格当前的颜色是什么.
最后我们扫描每一个小网格,求出每种颜色的总面积按序输出即可.
输出的时候注意is/are和 color/colors的区别.
AC代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=200+10;
struct Node
{
int x1,y1,x2,y2,c;//c是颜色
}nodes[maxn];
int n;
int num1,num2;
int x[maxn],y[maxn];
int color[maxn][maxn];
int main()
{
int w,h,kase=0;
while(scanf("%d%d",&h,&w)==2 && h)
{
if(kase>0) printf("\n");
num1=num2=0;
memset(color,0,sizeof(color));
scanf("%d",&n);
for(int i=0;i<n;++i)
{
scanf("%d%d%d%d%d",&nodes[i].x1,&nodes[i].y1,&nodes[i].x2,&nodes[i].y2,&nodes[i].c);
x[num1++]=nodes[i].x1;
x[num1++]=nodes[i].x2;
y[num2++]=nodes[i].y1;
y[num2++]=nodes[i].y2;
}
sort(x,x+num1);
sort(y,y+num2);
num1=unique(x,x+num1)-x;
num2=unique(y,y+num2)-y;
for(int i=0;i<n;++i)
{
int L_x=lower_bound(x,x+num1,nodes[i].x1)-x;
int R_x=lower_bound(x,x+num1,nodes[i].x2)-x;
int L_y=lower_bound(y,y+num2,nodes[i].y1)-y;
int R_y=lower_bound(y,y+num2,nodes[i].y2)-y;
for(int j=L_x;j<R_x;++j)
for(int k=L_y;k<R_y;++k)
color[j][k]=nodes[i].c;//着色
}
int area[maxn];//每种颜色的面积
memset(area,0,sizeof(area));
int ans=0;//还剩多少种颜色
for(int i=0;i<num1;++i)
for(int j=0;j<num2;++j)
if(color[i][j]) area[color[i][j]] += (x[i+1]-x[i])*(y[j+1]-y[j]);
printf("Case %d:\n",++kase);
for(int i=1;i<=100;++i)if(area[i])
{
printf("%d %d\n",i,area[i]);
++ans;
}
printf("There %s %d %s left on the wall.\n",ans>1?"are":"is",ans,ans>1?"colors":"color");
}
return 0;
}
分享到:
相关推荐
zoj 1610 Count the Colors.md
ZOJ解题报告ZOJ解题报告ZOJ解题报告ZOJ解题报告
zoj 1255 The Path.md
zoj题目简单归类zoj题目简单归类zoj题目简单归类
包含了zoj700多道题目的源代码,在做题时可以参考
zoj 1810 The Gourmet Club.md
zoj 2499 The Happy Worm.md
zoj 2151 The Highest Profits.md
acm中zoj1002的可运行C++程序
Problem Arrangement zoj 3777
ZOJ题目答案源码
zoj 1003 c语言的,要写这么多描述吗。。
一个非常非常非常非常实用的zoj结题代码
学习ACM程序设计的朋友一定要看,这是训练必备的POJ ZOJ题目分类及解题思路
ZOJ1805代码
The reason is that when the director chooses the words from the dictionary and encrypts them, he never changes their order (the words in the dictionary are lexicographically sorted). String a1a2 ... ...
本代码是zoj上AC的1951的代码,把双重循环简化为O(n),不过素数判断的改进还不够
zoj1027解题指南和代码,还不错,是学校培训给的。
浙大ZOJ题目分类,可以让你更方便快速锁定那你想要联系的题目,是自己快速提高·
ZOJ题解集合-截至2835。共1244个文件,C/C++,有重复