Shaping Regions

问题描述:

N个不同的颜色的不透明的长方形(1 <= N <= 1000)被放置在一张宽为A长为B的白纸上。
这些长方形被放置时，保证了它们的边于白纸的边缘平行。
所有的长方形都放置在白纸内，所以我们会看到不同形状的各种颜色。
坐标系统的原点(0,0)设在这张白纸的左下角，而坐标轴则平行于边缘。
求俯视能看到的颜色和该颜色的面积.

问题分析:

这个问题可以模拟,但是模拟有很多办法.
1.染色,给每个放入的矩形在白纸染色
2.线段树的扩展矩形树
3.矩形切割
等等

这里讨论矩形切割的算法

条件假设:
题目条件
矩形的边于白纸的边缘平行。
所有的矩形都放置在白纸内
坐标系统的原点(0,0)设在这张白纸的左下角，而坐标轴则平行于边缘。

模型的建立
假设两个矩形有重复部分,且A在B的上面,则B可以被看见的部分是B-B∩A.
这个B-B∩A,的部分不一定是一个矩形,那么我们可以将它变为矩形.
这样就得到三个矩形.
假设n个矩形都有重复部分,也可以逐个按此方法进行分解.

符号及变量说明
用oblong[i]来表示矩形i,它含有5个量
llx,lly,urx,ury,colour,分别表示左下角x轴坐标,左下角y轴坐标,右上角x轴坐标,右上角x轴坐标.

模型的求解
当一个矩形oblong[i]和oblong[j]重复,且j在i的上方时,可以将矩形i这样分解.
若oblong[j].llx>oblong[i].llx,则新产生的矩形oblong[new].urx:=oblong[j].llx,就是分割出原矩形以两矩形相交的位置向左的部分.
若oblong[j].urx 这样原矩形就剩下oblong[j].llx和oblong[j].urx中间的部分了.
若oblong[j].lly>oblong[i].lly,则新产生的矩形oblong[new].ury:=oblong[j].lly,就是分割出原矩形以两矩形相交的位置向下的部分.
若oblong[j].ury 如此将一个矩形分割,可以利用一个递归的过程求解问题.

USACO的分析...

Analysis by Mathijs Vogelzang

A straightforward approach to this problem would be to make an array which represents the table, and then draw all the rectangles on it. In the end, the program can just count the colors from the array and output them. Unfortunately, the maximum dimensions of this problem are 10,000 x 10,000, which means the program uses 100 million integers. That's too much, so we need another approach.

An approach that does work for such large cases (and it actually is a lot faster too) is to keep track of the rectangles, and delete portions of them when they are covered by other rectangles.

Consider this input set:

0 0 10 10 5
5 0 15 10 10

The program first reads in the first rectangle and puts it in a list. When it reads a new rectangle it checks all items in the list if they overlap with the new rectangle. This is the case, and then it deletes the old rectangle from the list and adds all parts which aren't covered to the list. (So in this case, the program would delete the first rectangle, add 0 0 5 10 5 to the list and then add the second rectangle to the list). ``

If you're unlucky, a new rectangle can create lots of new rectangles (when the new rectangle entirely fits into another one, the program creates four new rectangles which represent the leftover border:

+--------+      +-+--+--+
|        |      | |2 |  |
|        |      + +--+  |
|  +-+   |  --> | |  |  |
|  +-+   |      |1|  |3 |
|        |      | +--+  |
|        |      | | 4|  |
+--------+      +-+--+--+

This is not a problem however, because there can be only 2500 rectangles and there is plenty of memory, so rectangles have to be cut very much to run out of memory.

Note that with this approach, the only thing that matters is how many rectangles there are and how often they overlap. The maximum dimensions can be as large as you want, it doesn't matter for the running time.

Further Analysis by Tomek Czajka

There is another solution to this problem, which runs in O(n*n*log n) time, but is quite tricky. First, we add one big white rectangle at the bottom - the paper. Then we make two arrays: one containing all vertical edges of the rectangles, and the other the horizontal ones. For each edge we have its coordinates and remember, whether it's the left or right edge (top or bottom). We sort these edges from left to right and from top to bottom. Then we go from left to right (sweep), jumping to every x-coordinate of vertical edges. At each step we update the set of rectangles seen. We also want to update the amount of each color seen so far. So for each x we go from top to bottom, for each y updating the set of rectagles at a point (in the structure described below) and choosing the top one, so that we can update the amounts of colors seen.

The structure to hold the set of rectangles at a point should allow adding a rectangle (number from 1..1000), deleting a rectangle, and finding the top one. We can implement these operations in O(log n) time if we use a heap. To make adding and deleting run in O(log n) we must also have for each rectangle its position in the heap.

So the total time spent at each point is O(log n). Thus the algorithm works in O(n*n*log n) time.

And a solution from mrsigma:

#include 
#include 
#include 

FILE *fp,*fo;

struct rect
{
    int c;
    int x1,y1,x2,y2;
};

int c[2501];
rect r[10001];

int intersect(rect a,const rect &b,rect out[4])
{
    /* do they at all intersect? */
    if(b.x2=a.x2)
        return 0;
    if(b.y2=a.y2)
        return 0;
    /* they do */

    rect t;

    if(b.x1<=a.x1&&b.x2>=a.x2&&b.y1<=a.y1&&b.y2>=a.y2)
            return -1;

    /* cutting `a' down to match b */
    int nout=0;
    if(b.x1>=a.x1) {
        t=a,t.x2=b.x1;
        if(t.x1!=t.x2)
            out[nout++]=t;
        a.x1=b.x1;
    }
    if(b.x2        t=a,t.x1=b.x2;
        if(t.x1!=t.x2)
            out[nout++]=t;
        a.x2=b.x2;
    }
    if(b.y1>=a.y1) {
        t=a,t.y2=b.y1;
        if(t.y1!=t.y2)
            out[nout++]=t;
        a.y1=b.y1;
    }
    if(b.y2        t=a,t.y1=b.y2;
        if(t.y1!=t.y2)
            out[nout++]=t;
        a.y2=b.y2;
    }
    return nout;
}

int main(void) {
    fp=fopen("rect1.in","rt");
    fo=fopen("rect1.out","wt");

    int a,b,n;
    fscanf(fp,"%d %d %d",&a,&b,&n);

    r[0].c=1;
    r[0].x1=r[0].y1=0;
    r[0].x2=a;
    r[0].y2=b;

    rect t[4];

    int i,j,rr=1;
    for(i=0;i        int tmp;
        fscanf(fp,"%d %d %d %d %d",&r[rr].x1,&r[rr].y1,&r[rr].x2,&r[rr].y2,&r[rr].c);

        if(r[rr].x1>r[rr].x2) {
            tmp=r[rr].x1;
            r[rr].x1=r[rr].x2;
            r[rr].x2=tmp;
        }
        if(r[rr].y1>r[rr].y2) {
            tmp=r[rr].y1;
            r[rr].y1=r[rr].y2;
            r[rr].y2=tmp;
        }

        int nr=rr;
        rect curr=r[rr++];
        for(j=0;j            int n=intersect(r[j],curr,t);
            if(!n)
                continue;
            if(n==-1) {
                memmove(r+j,r+j+1,sizeof(rect)*(rr-j-1));
                j--;
                rr--;
                nr--;
                continue;
            }
            r[j]=t[--n];
            for(;n-->0;)
                r[rr++]=t[n];
        }
    }

    for(i=0;i        c[r[i].c]+=(r[i].x2-r[i].x1)*(r[i].y2-r[i].y1);

    for(i=1;i<=2500;i++)
        if(c[i])
            fprintf(fo,"%d %d\n",i,c[i]);

    return 0;
}