USACO Window Area

本人先使用数组模拟双向链表解决各个矩形位置的问题（看题解后发现是小题大作，只要给每个矩形定义一个“高度”就可以了）。
对于求露出的面积，把所求面积的矩形的x坐标离散化，y坐标使用类似线段覆盖的方法解决（与本人在Shaping Regions中采用的方法相似）。这种方法效率不是很高，最长测试点耗时约0.74s。

有几个细节需要注意：
1、输入坐标不全是小的在前的，因此要判断。
2、所给范围是前开后闭的，本人的处理方法是把更大的坐标-1.
3、读入指令时要一行一行读，特别小心换行符，本人先读入到tmp字串中，然后用sscanf格式读入。

USACO参考程序用的是矩形切割和漂浮法，本人正在理解中。
高度标记+漂浮法的代码放在本文末尾。漂浮法虽然用的是递归，但是速度很快，最长耗时：

Test 10: TEST OK [0.022 secs, 2128 KB]

用漂浮法需要先判断两个矩形是否有相交部分。漂浮法不需要把坐标-1

代码如下：

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

001 #include <stdio.h>
002 #include <stdlib.h>
003 #include <string.h>
004
005 typedef struct board
006 {
007     int x1,x2,y1,y2;
008     double sq;
009 }BOARD;
010
011 typedef struct seg
012 {
013     int b,e;
014     _Bool use;
015     struct seg *next;
016 }SEG;
017
018 int next[128];
019 int prev[128];
020 int alive[128];
021 int tot;
022 int b,t;
023 BOARD w[128];
024 SEG *first[32768];
025
026 int getmin(int a,int b)
027 {
028     if(a < b)    return a;
029     return b;
030 }
031
032 int getmax(int a,int b)
033 {
034     if(a > b)    return a;
035     return b;
036 }
037
038 void add(int i,int x1,int y1,int x2,int y2)
039 {
040     alive[i] = 1;
041     if(tot == 0)
042     {
043         b = t = i;
044         next[i] = 0;
045     }
046     else
047     {
048         next[i] = t;
049         t = i;
050     }
051     tot ++;
052     prev[i] = 0;
053     prev[next[i]] = i;
054     w[i].x1 = getmin(x1,x2);
055     w[i].x2 = getmax(x1,x2) - 1;
056     w[i].y1 = getmin(y1,y2);
057     w[i].y2 = getmax(y1,y2) - 1;
058     w[i].sq = (w[i].x2 - w[i].x1 + 1) * (w[i].y2 - w[i].y1 + 1);
059 }
060
061 void destroy(int i)
062 {
063     alive[i] = 0;
064     if(i == t)
065     {
066         t = next[i];
067         prev[t] = 0;
068     }
069     else if(i == b)
070     {
071         b = prev[i];
072         next[b] = 0;
073     }
074     else
075     {
076         next[prev[i]] = next[i];
077         prev[next[i]] = prev[i];
078     }
079     tot --;
080 }
081
082 void top(int i)
083 {
084     if(i == t)    return;
085     destroy(i);
086     alive[i] = 1;
087     tot ++;
088     next[i] = t;
089     prev[i] = 0;
090     prev[t] = i;
091     t = i;
092 }
093
094 void bottom(int i)
095 {
096     if(i == b)    return;
097     destroy(i);
098     alive[i] = 1;
099     tot ++;
100     prev[i] = b;
101     next[i] = 0;
102     next[b] = i;
103     b = i;
104 }
105
106 void chain()    //for debug
107 {
108     int p;
109     for(p = t;p != 0;p = next[p])
110     {
111         printf("%c->",(char)p);
112         if(p == b)    break;
113     }
114     printf("\n");
115 }
116
117 void draw_init(BOARD a)
118 {
119     int i;
120     SEG *p;
121     for(i = a.x1;i <= a.x2;i ++)
122     {
123         p = malloc(sizeof(SEG));
124         p->b = a.y1;
125         p->e = a.y2;
126         p->next = NULL;
127         p->use = 1;
128         first[i] = p;
129     }
130 }
131
132 void del_seg(int x,int b,int e)
133 {
134     SEG *p,*tmp;
135     for(p = first[x];p != NULL;p = p->next)
136     {
137         if(p->use == 0)    continue;
138         if(b > p->e)    continue;
139         if(e < p->b)    continue;
140         if(b <= p->b && e >= p->e)   //whole covered
141         {p->use = 0;continue;}
142         if(b <= p->b && e < p->e)
143         {p->b = e + 1;continue;}
144         if(e >= p->e && b > p->b)
145         {p->e = b - 1;continue;}
146         if(b > p->b && e < p->e)    //split
147         {
148             tmp = malloc(sizeof(SEG));
149             tmp->use = 1;
150             tmp->b = e + 1;
151             tmp->e = p->e;
152             tmp->next = first[x];
153             first[x] = tmp;
154             p->e = b - 1;
155             continue;
156         }
157     }
158 }
159
160 void clean(int x1,int x2)
161 {
162     SEG *p,*tmp;
163     for(;x1 <= x2;x1 ++)
164     {
165         for(p = first[x1];p != NULL;)
166         {
167             tmp = p;
168             p = p->next;
169             free(tmp);
170         }
171         first[x1] = NULL;
172     }
173 }
174
175 void percent(int i)
176 {
177     if(i == t)
178     {printf("100.000\n");return;}
179     int l,k;
180     long cnt = 0;
181     SEG *p;
182     draw_init(w[i]);
183     for(k = t;k != i;k = next[k])
184         for(l = w[k].x1;l <= w[k].x2;l ++)
185             del_seg(l,w[k].y1,w[k].y2);
186     for(l = w[i].x1;l <= w[i].x2;l ++)
187         for(p = first[l];p !=NULL;p = p->next)
188             if(p->use)    cnt += p->e - p->b + 1;
189     printf("%.3lf\n",(100.0 * cnt) / w[i].sq);
190     clean(w[i].x1,w[i].x2);
191 }
192
193 int main()
194 {
195     char c,i,tmp[30];
196     int x1,x2,y1,y2;
197     freopen("window.in","r",stdin);
198     freopen("window.out","w",stdout);
199     while(!feof(stdin))
200     {
201         c = getchar();
202         if(c == 'w')
203         {
204             scanf("%s\n",tmp);
205             sscanf(tmp,"(%c,%d,%d,%d,%d)\n",&i,&x1,&y1,&x2,&y2);
206             add((int)i,x1,y1,x2,y2);
207         }
208         else if(c == 't')
209         {
210             scanf("%s\n",tmp);
211             sscanf(tmp,"(%c)\n",&i);
212             top((int)i);
213         }
214         else if(c == 'b')
215         {
216             scanf("%s\n",tmp);
217             sscanf(tmp,"(%c)\n",&i);
218             bottom((int)i);
219         }
220         else if(c == 'd')
221         {
222             scanf("%s\n",tmp);
223             sscanf(tmp,"(%c)\n",&i);
224             destroy((int)i);
225         }
226         else if(c == 's')
227         {
228             scanf("%s\n",tmp);
229             sscanf(tmp,"(%c)\n",&i);
230             percent((int)i);
231         }
232     }
233     return 0;
234 }

漂浮法的代码：

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

001 #include <stdio.h>
002 #include <stdlib.h>
003 #include <string.h>
004
005 typedef struct board
006 {
007     long x1,x2,y1,y2;
008 }BOARD;
009
010 int height[128];
011 int alive[128];
012 int bottom,top;
013 BOARD w[128];
014
015 int getmin(int a,int b)
016 {
017     if(a < b)    return a;
018     return b;
019 }
020
021 int getmax(int a,int b)
022 {
023     if(a > b)    return a;
024     return b;
025 }
026
027 long cover(BOARD *p)
028 {
029     return (p->x2 - p->x1) * (p->y2 - p->y1);
030 }
031
032 void add(int i,int x1,int y1,int x2,int y2)
033 {
034     alive[i] = 1;
035     height[i] = ++top;
036     w[i].x1 = getmin(x1,x2);
037     w[i].x2 = getmax(x1,x2);
038     w[i].y1 = getmin(y1,y2);
039     w[i].y2 = getmax(y1,y2);
040 }
041
042 void destroy(int i)
043 {
044     alive[i] = 0;
045 }
046
047 void puttop(int i)
048 {
049     height[i] = ++top;
050 }
051
052 void putbottom(int i)
053 {
054     height[i] = --bottom;
055 }
056
057 long cansee;
058
059 int havecommon(BOARD *a,BOARD *b)
060 {
061     if(a->x1 > b->x2)    return 0;
062     if(a->x2 < b->x1)    return 0;
063     if(a->y1 > b->y2)    return 0;
064     if(a->y2 < b->y1)    return 0;
065     return 1;
066 }
067
068 void float_up(int now,BOARD p,int h)
069 {
070     if(p.x1 >= p.x2 || p.y1 >= p.y2)    return;
071     if(now == 128)
072     {
073         fprintf(stderr,"%ld %ld %ld %ld\n",p.x1,p.y1,p.x2,p.y2);
074         cansee += cover(&p);
075         return;
076     }
077     if(alive[now] && height[now] > h && havecommon(&w[now],&p))
078     {
079         BOARD tmp;
080         //Left
081         tmp.y1 = p.y1;
082         tmp.y2 = p.y2;
083         tmp.x1 = p.x1;
084         tmp.x2 = w[now].x1;
085         float_up(now + 1,tmp,h);
086         //Right
087         tmp.x1 = w[now].x2;
088         tmp.x2 = p.x2;
089         float_up(now + 1,tmp,h);
090         //Top
091         tmp.x1 = getmax(w[now].x1,p.x1);
092         tmp.x2 = getmin(w[now].x2,p.x2);
093         tmp.y1 = w[now].y2;
094         tmp.y2 = p.y2;
095         float_up(now + 1,tmp,h);
096         //Bottom
097         tmp.y2 = w[now].y1;
098         tmp.y1 = p.y1;
099         float_up(now + 1,tmp,h);
100     }
101     else    float_up(now + 1,p,h);
102 }
103
104 void percent(int i)
105 {
106     double p;
107     cansee = 0;
108     float_up(0,w[i],height[i]);
109     p = ((double)cansee) / ((double)cover(&w[i]));
110     printf("%.3lf\n",100.0 * p);
111 }
112
113 int main()
114 {
115     char c,i,tmp[30];
116     long x1,x2,y1,y2;
117     freopen("window.in","r",stdin);
118     freopen("window.out","w",stdout);
119     top = 0;
120     bottom = 0;
121     while(!feof(stdin))
122     {
123         c = getchar();
124         if(c == 'w')
125         {
126             scanf("%s\n",tmp);
127             sscanf(tmp,"(%c,%ld,%ld,%ld,%ld)\n",&i,&x1,&y1,&x2,&y2);
128             add((int)i,x1,y1,x2,y2);
129         }
130         else if(c == 't')
131         {
132             scanf("%s\n",tmp);
133             sscanf(tmp,"(%c)\n",&i);
134             puttop((int)i);
135         }
136         else if(c == 'b')
137         {
138             scanf("%s\n",tmp);
139             sscanf(tmp,"(%c)\n",&i);
140             putbottom((int)i);
141         }
142         else if(c == 'd')
143         {
144             scanf("%s\n",tmp);
145             sscanf(tmp,"(%c)\n",&i);
146             destroy((int)i);
147         }
148         else if(c == 's')
149         {
150             scanf("%s\n",tmp);
151             sscanf(tmp,"(%c)\n",&i);
152             percent((int)i);
153         }
154     }
155     return 0;
156 }