HDU 1543 Paint the Wall（离散化+暴力）

浅浅的花香味﹌ 2022-06-10 11:28 143阅读 0赞

Here comes our future artist. See, he is painting again, this time on home's white wall, using different color of paint. Let me see, red, yellow, black, green... but why does he just paint rectangles? Pretty guy, seems he is fond of it.

So, after he's done his great job, the white wall has been filled with so many blocks of color. Of course, some color previously painted has been covered by some color painted later. Now, the little guy has some doubt that how many different colors have been left on the wall, and what are the areas of them. As a seven-year-old boy, he has just learned painting in kindergarten, math seems too difficult for him. So he turns to you, a college student good at math and programming, to help him figuring it out. Don't make him disappointed.

Input

Input consists of multiple test cases, each describing "a great job" done by out little guy.

Each case begins with a line containing two integers, *Height* and *Width*, the size of the wall. The next line contains an integer *N*, which is the number of rectangles that have been painted. *N* lines follow, describing the rectangles in the order they were painted. Each line contains five integers, *Top*, *Left*, *Bottom*, *Right*, and *Color*, giving out the position, size and color information of the rectangle.

The range of *Height* and *Width* is \[1, 10000\]. There will be at least 1, and at most 100 rectangles to be painted. For each rectangle, *Top* and *Bottom* is in the range \[0, *Height*\], *Left* and *Right* is in the range \[0, *Width*\]. *Bottom* is strictly greater than *Top*, and *Right* is strictly greater than *Left*. *Color* will be in the range \[1, 100\].

The top-left coordinate of the wall is (0, 0), and the bottom-right coordinate of the wall is (*Height*, *Width*), as shown below.

(0,0)      (0,W)
    ---------------
    |             |
    |             |
    |             |
    |             |
    |             |
    ---------------
    (H,0)      (H,W)

The last case is followed by a line containing two zeroes.

There is a blank line between two test cases.

Output

For each painting, first output "Case *X*:" in a single line where *X* is the case number starting form 1. Then output the colors left and their areas, one color per line, in the order of color numbers (increasing). For each color, you should output the color number, a blank space, and the area of this color on the wall. After that, you should output a single line "There is *M* color left on the wall." or "There are *M*colors left on the wall.", depending on *M*, which is the number of colors left on the wall.

Output a blank line between two test cases.

Sample Input

10 5
    1
    1 1 2 2 2
    
    4 4
    2
    0 0 3 3 1
    2 2 4 4 2
    
    0 0

Sample Output

Case 1:
    2 1
    There is 1 color left on the wall.
    
    Case 2:
    1 8
    2 4
    There are 2 colors left on the wall.

题解：

题意：

有一面n\*m的大墙，每次往墙上涂上一些不同颜色的油漆，输入开始图油漆的矩形的左上角和结束的右下角，和油漆的种类，问最后又多少种油漆在墙上，他们的面积分别是多少

思路：

乍一看是一个扫描线或者二维线段树，仔细一看数据范围就100个矩形，完全不用那么麻烦（我看了他们二维线段树做法时间是40ms，代码是我长度的一倍，而我暴力的做法时间是0ms），处理数据范围比较大这题根本就不是个事，直接离散化所有端点，然后每次扫一个矩形的时候在离散化后的数组里面用二分找一下，类似于模拟的做法用个二重循环涂一遍就好了，最后计算的时候直接全部扫一遍，一个格子一个格子计算面积累加起来就行了

代码：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<vector>
    #include<deque>
    using namespace std;
    #define lson k*2
    #define rson k*2+1
    #define M (t[k].l+t[k].r)/2
    #define INF 1008611111
    #define ll long long
    #define eps 1e-15
    int xx[205];//离散化后端点最多200个
    int yy[205];
    int p[205][205];//离散化后的端点覆盖情况
    int si[105];//存每种颜色的面积
    struct edge
    {
        int x1,x2,y1,y2;
        int c;//颜色
    }a[105];//存矩阵的信息
    int main()
    {
        int i,j,k,n,m,ans,tot,q,len1,len2,cas=1,tag=0;
        while(scanf("%d%d",&n,&m)!=EOF)
        {
            if(n==0&&m==0)
                break;
            if(tag)
                printf("\n");
            scanf("%d",&q);
            tot=0;
            for(i=0;i<q;i++)
            {
                scanf("%d%d%d%d%d",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2,&a[i].c);
                xx[tot]=a[i].x1;
                xx[tot+1]=a[i].x2;
                yy[tot]=a[i].y1,
                yy[tot+1]=a[i].y2;
                tot+=2;
            }
            sort(xx,xx+tot);
            sort(yy,yy+tot);//排序后离散化
            len1=unique(xx,xx+tot)-xx;
            len2=unique(yy,yy+tot)-yy;
            memset(p,0,sizeof(p));
            memset(si,0,sizeof(si));
            for(i=0;i<q;i++)
            {
                int st1=lower_bound(xx,xx+len1,a[i].x1)-xx;
                int end1=lower_bound(xx,xx+len1,a[i].x2)-xx;//二分查找起始点
                int st2=lower_bound(yy,yy+len2,a[i].y1)-yy;
                int end2=lower_bound(yy,yy+len2,a[i].y2)-yy;
                for(j=st1;j<end1;j++)//二重循环搞的去
                {
                    for(k=st2;k<end2;k++)
                    {
                        p[j][k]=a[i].c;
                    }
                }
            }
            for(i=0;i<len1-1;i++)//扫描全图
            {
                for(j=0;j<len2-1;j++)
                {
                    if(p[i][j])
                    {
                        si[p[i][j]]+=((xx[i+1]-xx[i])*(yy[j+1]-yy[j]));//每个格子代表的面积
                    }
                }
            }
            printf("Case %d:\n",cas);
            cas++;
            int ans=0;
            for(i=1;i<=100;i++)//输出
            {
                if(si[i]!=0)
                {
                    printf("%d %d\n",i,si[i]);
                    ans++;
                }
            }
            if(ans==1)//这里是个坑，就因为这个wa了一次
                printf("There is %d color left on the wall.\n",ans); 
            else
                printf("There are %d colors left on the wall.\n",ans);
            tag=1;
        }
        return 0;
    }