POJ 1151

题目大意：给出n个矩形（通过给出对角坐标确定），这些矩形间可能有重叠，求除去重叠后覆盖的面积是多少。
解：矩形切割，只是用线段树去维护线段达到logn的效率。
View Code
  1 //poj 1151
  2 const
  3         maxn=1111;
  4         inf='1.txt';
  5 type
  6         type_node=record
  7           mid, l, r, flag: longint;
  8           x1, x2, cnt: double;
  9         end;
 10         type_line=record
 11           x1, x2, y: double;
 12           op: longint;
 13         end;
 14 var
 15         tree: array[0..maxn*4*2]of type_node;
 16         x: array[0..maxn*2]of double;
 17         line: array[0..maxn*2]of type_line;
 18         tot, test, n: longint;
 19         ans: double;
 20 procedure _add(x1, x2, yy: double; zz: longint);
 21 begin
 22   inc(tot);
 23   line[tot].x1 := x1; line[tot].x2 := x2;
 24   line[tot].y := yy; line[tot].op := zz;
 25 end;
 26 
 27 procedure _sortline(b, e: longint);
 28 var
 29         i, j: longint;
 30         x: double;
 31         k: type_line;
 32 begin
 33   i := b; j := e; x := line[(i+j)>>1].y;
 34   repeat
 35     while line[i].y>x do inc(i);
 36     while line[j].y<x do dec(j);
 37     if i<=j then begin
 38       k := line[i]; line[i] := line[j]; line[j] := k;
 39       inc(i); deC(j);
 40     end;
 41   until i>j;
 42   if j>b then _sortline(b, j);
 43   if i<e then _sortline(i, e);
 44 end;
 45 
 46 procedure _sortx(b, e: longint);
 47 var
 48         i, j: longint;
 49         xx, k: double;
 50 begin
 51   i := b; j := e; xx := x[(i+j)>>1];
 52   repeat
 53     while x[i]<xx do inc(i);
 54     while x[j]>xx do dec(j);
 55     if i<=j then begin
 56       k := x[i]; x[i] := x[j]; x[j] := k;
 57       inc(i); dec(j);
 58     end;
 59   until i>j;
 60   if j>b then _sortx(b, j);
 61   if i<e then _sortx(i, e);
 62 end;
 63 
 64 procedure _build(ll, rr, kk: longint);
 65 begin
 66   with tree[kk] do begin
 67     flag := 0; cnt := 0;
 68     x1 := x[ll]; x2 := x[rr];
 69     if ll+1>=rr then exit;
 70     mid := (ll+rr)>>1;
 71     l := kk << 1; _build(ll, mid, l);
 72     r := l + 1; _build(mid, rr, r);
 73   end;
 74 end;
 75 
 76 procedure _init;
 77 var
 78         i: longint;
 79         x1, x2, y1, y2: double;
 80 begin
 81   tot := 0; ans := 0;
 82   for i := 1 to n do begin
 83     readln(x1, y1, x2, y2);
 84     _add(x1, x2, y1, -1); x[tot] := x1;
 85     _add(x1, x2, y2, 1); x[tot] := x2;
 86   end;
 87   _sortline(1, tot);
 88   _sortx(1, tot);
 89   _build(1, tot, 1);
 90 end;
 91 
 92 procedure calc(k: longint);
 93 begin
 94   with tree[k] do begin
 95     if flag>0 then begin
 96       cnt := x2-x1;
 97       exit;
 98     end;
 99     if (l+r<>0) then cnt := tree[l].cnt+tree[r].cnt;
100   end;
101 end;
102 
103 procedure _cover(xx, yy: double; zz, k: longint);
104 begin
105   tree[k].cnt := 0;
106   if (xx<=tree[k].x1)and(tree[k].x2<=yy) then begin
107     inc(tree[k].flag, zz);
108     calc(k);
109     exit;
110   end;
111   if tree[k].mid=0 then exit;
112   if yy<=x[tree[k].mid] then _cover(xx, yy, zz, tree[k].l)
113     else if xx>=x[tree[k].mid] then _cover(xx, yy, zz, tree[k].r)
114       else begin
115         _cover(xx, x[tree[k].mid], zz, tree[k].l);
116         _cover(x[tree[k].mid], yy, zz, tree[k].r);
117       end;
118   calc(k);
119 end;
120 
121 procedure _main;
122 var
123         i: longint;
124 begin
125   _cover(line[1].x1, line[1].x2, line[1].op, 1);
126   for i := 2 to tot do begin
127     ans := ans + tree[1].cnt*(line[i-1].y-line[i].y);
128     _cover(line[i].x1, line[i].x2, line[i].op, 1);
129   end;
130 end;
131 
132 procedure _print;
133 begin
134   writeln('Test case #', test);
135   writeln('Total explored area: ', ans:0:2);
136 end;
137 
138 begin
139   assign(input,inf); reset(input);
140   fillchar(tree, sizeof(tree), 0);
141   test := 0;
142   readln(n);
143   while (n<>0) do begin
144     inc(test);
145     _init;
146     _main;
147     _print;
148     writeln;
149     readln(n);
150   end;
151 end.