Shaping Regions 解题报告

最先想到的方法是模拟，显然，空间不够。

然后想到二维线段树，空间依然不够。

题目中有一个提示：分割矩形。代码写了好久，没有调试清楚，放弃。

最后想到一个方法：对每个列单独进行线段覆盖。线段覆盖相对分割矩形情况就少了许多，调试难度也降低了，只不过由于每个列要独立操作，效率比分割矩形低(前10个数据耗时0s，第11个1.4s）。

代码如下，每列的线段用链表储存，以符合空间限制。

C语言: 高亮代码由发芽网提供

001 #include <stdio.h>
002 #include <stdlib.h>
003 #define MAX_WIDTH 10000 + 10
004 #define MAX_COLOR 2500 + 10
005
006 typedef struct node
007 {
008     int b,e;  //开始与结束位置，前闭后开
009     int c;   //颜色
010     struct node *prev,*next;  //双向链表，便于删除
011 }node;
012
013 node * root[MAX_WIDTH];  //链表头
014 long area[MAX_COLOR];  //储存每个颜色的面积
015
016 void sumup(int);
017 void paint(int,int,int,int);
018 void add(int,int,int,int,int);
019
020 int main()
021 {
022     freopen("rect1.in","r",stdin);
023     freopen("rect1.out","w",stdout);
024     int i;
025     int N;
026     int lx,ly,rx,ry,c;
027     int x,y;
028     scanf("%d%d%d",&x,&y,&N);
029     //先置整个平面颜色为1
030     for(i = 0;i < x;i ++)
031     {
032         root[i] = malloc(sizeof(node));
033         root[i]->b = 0;
034         root[i]->e = y;
035         root[i]->c = 1;
036         root[i]->next = root[i]->prev = NULL;
037     }
038     for(i = 0;i < N;i ++)
039     {
040         scanf("%d%d%d%d%d",&lx,&ly,&rx,&ry,&c);
041         add(lx,ly,rx,ry,c);
042     }
043     for(i = 0;i < x;i ++)
044         sumup(i);  //统计各列颜色面积
045     for(i = 1;i < MAX_COLOR;i ++)
046         if(area[i] > 0) printf("%d %ld\n",i,area[i]);
047     fclose(stdout);
048     fclose(stdin);
049     return 0;
050 }
051
052 void sumup(int col)
053 {
054     node *p;
055     for(p = root[col];p != NULL;p = p->next)
056         area[p->c] += p->e - p->b;
057 }
058
059 void add(int lx,int ly,int rx,int ry,int c)
060 {
061     int i;
062     for(i = lx;i < rx;i ++)
063         paint(ly,ry,c,i);   //对矩形所在每一列进行线段覆盖
064 }
065
066 void del(int i,node * p)
067 {
068     if(p->next != NULL)
069         p->next->prev = p->prev;
070     if(p == root[i])
071         root[i] = p->next;
072     else
073         p->prev->next = p->next;
074     free(p);
075 }
076
077 void insert(int i,node *p)
078 {
079     p->next = root[i];
080     p->prev = NULL;
081     root[i]->prev = p;
082     root[i] = p;
083 }
084
085 void paint(int b,int e,int c,int i)
086 {
087     node * tmp;
088     node * p = root[i];
089     //插入新线段
090     tmp = malloc(sizeof(node));
091     tmp->b = b;
092     tmp->e = e;
093     tmp->c = c;
094     insert(i,tmp);
095     while(p != NULL)
096     {
097         if(p->b >= p->e)
098         {
099             tmp = p;
100             p = p->next;
101             del(i,tmp);
102             //清除无效的线段
103         }
104         //根据位置关系修改原有线段
105         else if(p->b >= e || p->e <= b)
106             p = p->next;
107         else if(p->e <= e && p->b <= b)
108         {
109             p->e = b;
110             p = p->next;
111         }
112         else if(p->b >= b && p->e >= e)
113         {
114             p->b = e;
115             p = p->next;
116         }
117         else if(p->b >= b && p->e <= e)
118         {
119             tmp = p;
120             p = p->next;
121             del(i,tmp);
122         }
123         else
124         {
125             tmp = malloc(sizeof(node));
126             tmp->b = p->b;tmp->c = p->c;tmp->e = b;
127             insert(i,tmp);
128             p->b = e;
129             p = p->next;
130         }
131     }
132 }