poj 1177 Picture (线段树 扫描线 离散化 矩形周长并)

  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 = 10000+10;
 11 using namespace std;
 12 int n, x[maxn];
 13 struct node
 14 {
 15     int l, r, cnt;
 16     int lf, rf;
 17     int num, c; //num是分支的个数，即当前的x段有多少段，可以想象一段是对应两个竖边的。
 18     bool lc, rc;  //表示左端是否覆盖，和右端是否覆盖，用来判断x段是否练成一块了
 19 }tr[maxn*4];
 20 struct Line
 21 {
 22     int y, x1, x2, f;
 23 }line[maxn];
 24 bool cmp(Line a, Line b)
 25 {
 26     return a.y < b.y;
 27 }
 28 void build(int l, int r, int rt)
 29 {
 30     tr[rt].l = l; tr[rt].r = r;
 31     tr[rt].lf = x[l]; tr[rt].rf = x[r];
 32     tr[rt].cnt = 0; tr[rt].num = 0;
 33     tr[rt].c = 0;
 34     tr[rt].lc = tr[rt].rc = false;
 35     if(tr[rt].l+1 == tr[rt].r) return;
 36     int mid = (l+r)/2;
 37     build(l, mid, 2*rt);
 38     build(mid, r, 2*rt+1);
 39 }
 40 void calen(int rt)
 41 {
 42     if(tr[rt].c>0)
 43     {
 44         tr[rt].cnt = tr[rt].rf-tr[rt].lf;
 45         tr[rt].num = 1;
 46         tr[rt].lc = tr[rt].rc = true;  //这整个一块都覆盖了，左右端点自然也覆盖
 47         return;
 48     }
 49     if(tr[rt].l+1 == tr[rt].r)
 50     {
 51         tr[rt].cnt = tr[rt].num = 0;
 52         tr[rt].lc = tr[rt].rc = false;
 53     }
 54     else
 55     {
 56         tr[rt].cnt = tr[2*rt].cnt+tr[2*rt+1].cnt;
 57         tr[rt].lc = tr[2*rt].lc;  tr[rt].rc = tr[2*rt+1].rc;//自己这块没有覆盖，看一下子节点是否有覆盖
 58         tr[rt].num = tr[2*rt].num+tr[2*rt+1].num;
 59         if(tr[2*rt].rc && tr[2*rt+1].lc) tr[rt].num --;  //如果当前这个节点的子节点左的右
 60                         //覆盖和右的左覆盖说明中间已经练成一片了，所以分支-1
 61     }
 62 }
 63 void update(int rt, Line e)
 64 {
 65     if(tr[rt].lf==e.x1 && tr[rt].rf==e.x2)
 66     {
 67         tr[rt].c += e.f;
 68         calen(rt);
 69         return;
 70     }
 71     if(e.x2<=tr[2*rt].rf) update(2*rt, e);
 72     else if(e.x1>=tr[2*rt+1].lf) update(2*rt+1, e);
 73     else
 74     {
 75         Line tmp;
 76         tmp = e;
 77         tmp.x2 = tr[2*rt].rf;
 78         update(2*rt, tmp);
 79         tmp = e;
 80         tmp.x1 = tr[2*rt+1].lf;
 81         update(2*rt+1, tmp);
 82     }
 83     calen(rt);
 84 }
 85 int main()
 86 {
 87     int i, t, ans, pre;
 88     int x1, x2, y1, y2;
 89     while(~scanf("%d", &n))
 90     {
 91         t = 0; ans = 0; pre = 0;
 92         for(i = 0; i < n; i++)
 93         {
 94             scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
 95             line[t].x1 = x1; line[t].x2 = x2;
 96             line[t].y = y1; line[t].f = 1;
 97             x[t++] = x1;
 98             line[t].x1 = x1; line[t].x2 = x2;
 99             line[t].y = y2; line[t].f = -1;
100             x[t++] = x2;
101         }
102         sort(x, x+t);
103         sort(line, line+t, cmp);
104         int y = unique(x, x+t)-x;  //去重
105         build(0, y-1, 1);
106 
107         for(i = 0; i < t-1; i++)
108         {
109             update(1, line[i]);
110             ans += tr[1].num*2*(line[i+1].y-line[i].y); //竖线的长度
111             ans += abs(tr[1].cnt-pre); //加上 新增的横线 或者 是减少的横线
112             pre = tr[1].cnt;
113         }
114         update(1, line[i]);
115         ans += abs(tr[1].cnt-pre);
116         printf("%d
", ans);
117     }
118     return 0;
119 }