
题目:
桌面上放了N个平行于坐标轴的矩形,这N个矩形可能有互相覆盖的部分,求它们组成的图形的面积。
在翻题目时,偶然发现了这道标号为WA的题目。
原来,以前我把一中培训的代码发了上去,却WA了4个点,因此失去信心。
仔细研究了代码,却无异样,这是标准的离散思想(这里不再展开)。
报了“试一试”的心情,我把其他数组类型也开了int64,结果竟然AC了!
仔细一想,我发现尽管数组在longint范围内(-10^8------10^8),但是在运算的时候(极大值和极小值相减)仍会越界,还是开大为好!
以下为代码:
const max=101; var x1,x2,y1,y2:array[0..max] of int64; x,y,a,b:array[0..2*max] of int64; pop:boolean; h1,h2,i,j,k,n,h,t:longint; ans:qword; begin readln(n); h:=0; for i:=1 to n do begin readln(x1[i],y1[i],x2[i],y2[i]); inc(h); x[h]:=x1[i];y[h]:=y1[i]; inc(h); x[h]:=x2[i];y[h]:=y2[i]; end; for i:=1 to h-1 do for j:=i+1 to h do if x[i]>x[j] then begin t:=x[i]; x[i]:=x[j]; x[j]:=t; end; for i:=1 to h-1 do for j:=i+1 to h do if y[i]>y[j] then begin t:=y[i]; y[i]:=y[j]; y[j]:=t; end; h1:=1; a[1]:=x[1]; for i:=2 to h do if x[i]<>x[i-1] then begin inc(h1); a[h1]:=x[i]; end; h2:=1; b[1]:=y[1]; for i:=2 to h do if y[i]<>y[i-1] then begin inc(h2); b[h2]:=y[i]; end; for i:=1 to h1-1 do for j:=1 to h2-1 do begin pop:=false; for k:=1 to ndo if (a[i]>=x1[k])and (a[i+1]<=x2[k]) and (b[j]>=y1[k]) and (b[j+1]<=y2[k])then begin pop:=true; break; end; if pop thenans:=ans+(b[j+1]-b[j])*(a[i+1]-a[i]); end; writeln(ans); end.