poj 1151 Atlantis （离散化 + 扫描线 + 线段树 矩形面积并）

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <vector>
  4 #include <cstring>
  5 #include <cstdlib>
  6 #include <algorithm>
  7 #define LL __int64
  8 #define lson l, mid, 2*rt
  9 #define rson mid+1, r, 2*rt+1
 10 const int maxn = 200+10;
 11 using namespace std;
 12 int n;
 13 double y[maxn];
 14 struct node
 15 {
 16     int l, r, c;  //l, r记录左右节点，c记录覆盖情况
 17     double cnt, lf, rf; //cnt记录这一段当前的长度，lf,rf记录这一段实际的边界
 18 }tr[4*maxn];
 19 struct Line
 20 {
 21     double x, y1, y2; //x记录该段x坐标，y1,y2记录该段投影的y边界
 22     int f;
 23 }line[maxn]; //记录在y轴上的投影,f=1表示线段的开始，f=-1表示线段的结束
 24 bool cmp(Line a, Line b)
 25 {
 26     return a.x < b.x;
 27 }
 28 void build(int l, int r, int rt)
 29 {
 30     tr[rt].l = l; tr[rt].r = r;
 31     tr[rt].cnt = tr[rt].c = 0;
 32     tr[rt].lf = y[l]; tr[rt].rf = y[r];  //相当于离散化，把实际左右坐标离散成l，r
 33     if(l+1==r) return;
 34     int mid = (l+r)/2;
 35     build(l, mid, 2*rt);
 36     build(mid, r, 2*rt+1);  //注意是mid,不是mid+1，因为要所有段覆盖
 37 }
 38 void calen(int rt)
 39 {
 40     if(tr[rt].c>0)  //如果这段被覆盖，就更新这段的长度为实际长度
 41     {
 42         tr[rt].cnt = tr[rt].rf-tr[rt].lf;
 43         return;
 44     }
 45     if(tr[rt].l+1==tr[rt].r) tr[rt].cnt = 0; //如果这段被撤销，而且是最后的就把长度变为0
 46     else tr[rt].cnt = tr[2*rt].cnt+tr[2*rt+1].cnt; //如果被撤销但不是最后的，就加一下左右
 47 }
 48 void update(int rt, Line e) //加入或者减去一条线段后的更新
 49 {
 50     if(e.y1==tr[rt].lf && e.y2==tr[rt].rf)
 51     {
 52         tr[rt].c += e.f;  //改变覆盖情况
 53         calen(rt);
 54         return;
 55     }
 56     if(e.y2<=tr[2*rt].rf) update(2*rt, e);
 57     else if(e.y1>=tr[2*rt+1].lf) update(2*rt+1, e);
 58     else  //跨区间的情况
 59     {
 60         Line tmp = e;
 61         tmp.y2 = tr[2*rt].rf;
 62         update(2*rt, tmp);
 63         tmp = e;
 64         tmp.y1 = tr[2*rt+1].lf;
 65         update(2*rt+1, tmp);
 66     }
 67     calen(rt);
 68  }
 69 int main()
 70 {
 71     int i, ca=1, cnt;
 72     double x1, x2, y1, y2, ans;
 73     while(~scanf("%d", &n)&&n)
 74     {
 75         cnt = 1; ans = 0;
 76         for(i = 0; i < n; i++)
 77         {
 78             scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
 79             line[cnt].x = x1; line[cnt].y1 = y1;
 80             line[cnt].y2 = y2; line[cnt].f = 1;
 81             y[cnt++] = y1;
 82             line[cnt].x = x2; line[cnt].y1 = y1;
 83             line[cnt].y2 = y2; line[cnt].f = -1;
 84             y[cnt++] = y2;
 85         }
 86         cnt--;
 87         sort(line+1, line+cnt+1, cmp);  //按x从小到大排序
 88         sort(y+1, y+cnt+1); //按照y排序
 89         build(1, cnt, 1);
 90 
 91         update(1, line[1]);
 92         for(i = 2; i <= cnt; i++)
 93         {
 94             ans += tr[1].cnt*(line[i].x-line[i-1].x); //tr[1].cnt记录全段中当前覆盖的值
 95             update(1, line[i]); 
 96         }
 97         printf("Test case #%d
", ca++);
 98         printf("Total explored area: %.2lf

", ans);
 99     }
100     return 0;
101 }