解题思路:

总体思路:

1.沿X轴离散化建树

2.按Y值从小到大排序平行与X轴的边,然后顺序处理

如果遇到矩形下面那条边则插入到线段树中,遇到矩形上面的边则将相应的边删除掉

根据线段树当前的状态统计长度

第二点是本题的核心思想,偶再举个例:

第一次求出的部分很好理解.

第二次求出的为什么会少了中间那部分.那是因为插入的新线段覆盖了第一条,此时线段树返回的长度是新的那一条的长度,将这个值再减去上次的就少了中间那部分

第三次因为是矩形的上边,所以要删除在那条长的线段.此时的线段树返回的则是第一次的长度,将此值减去第二次返回值,再取其负值就是红色X轴那部分了

最后那条X轴的,再补上就行了.

需要注意的就是离散化以后一定要去掉重复元素，否则会出错的。

转载自:传送门

AC代码:

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<algorithm>
  4 
  5 using namespace std;
  6 
  7 struct kkk {
  8     int l,r;//线段树表示区间范围 
  9     int cnt;//有效长度 
 10     int lf,rf;//实际左右端点 
 11     int numseg;//分支数,一个分支对应两条竖线 
 12     int c;//记录覆盖情况 
 13     bool lc,rc;//左右半覆盖情况 
 14 }s[40040];
 15 
 16 struct ll {
 17     int y;
 18     int x1,x2;
 19     int f;//表示出入边,入边为1,出边为-1(自己想想为什么) 
 20 }l[10010];
 21 
 22 int x[10010];
 23 
 24 bool cmp(ll a,ll b) {
 25     return a.y < b.y;
 26 }
 27 
 28 void build(int i,int le,int r) {//建树 
 29     s[i].l = le;
 30     s[i].r = r;
 31     s[i].lf = x[le];
 32     s[i].rf = x[r];
 33     s[i].cnt = 0;
 34     s[i].numseg = 0;
 35     s[i].c = 0;
 36     s[i].lc = s[i].rc = false;
 37     if(le + 1 == r) return ;
 38     int mid = (le + r) / 2;
 39     build(i << 1,le,mid);
 40     build((i << 1) | 1,mid,r);
 41 }
 42 
 43 void calen(int i) {//计算长度 
 44     if(s[i].c > 0) {
 45         s[i].cnt = s[i].rf - s[i].lf;
 46         s[i].numseg = 1;
 47         s[i].lc = s[i].rc = true;
 48         return ;
 49     }
 50     if(s[i].l + 1 == s[i].r) {
 51         s[i].cnt = 0;
 52         s[i].numseg = 0;
 53         s[i].lc = s[i].rc = false;
 54     }
 55     else {
 56         s[i].cnt = s[i<<1].cnt + s[(i<<1)|1].cnt;
 57         s[i].lc = s[i<<1].lc;
 58         s[i].rc = s[(i<<1)|1].rc;
 59         s[i].numseg = s[i<<1].numseg + s[(i<<1)|1].numseg;
 60         if(s[i<<1].rc&&s[(i<<1)|1].lc) s[i].numseg--;
 61     }
 62 }
 63 
 64 void update(int i,ll e) {
 65     if(s[i].lf == e.x1 && s[i].rf == e.x2) {
 66         s[i].c += e.f;
 67         calen(i);
 68         return ;
 69     }
 70     if(e.x2 <= s[i<<1].rf) update(i << 1,e);
 71     else if(e.x1 >= s[(i<<1)|1].lf) update((i<<1) | 1,e);
 72     else {
 73         ll temp = e;
 74         temp.x2 = s[i<<1].rf;
 75         update(i << 1,temp);
 76         temp = e;
 77         temp.x1 = s[i<<1|1].lf;
 78         update((i<<1)|1,temp);
 79     }
 80     calen(i);
 81 }
 82 
 83 int main()
 84 {
 85     int x1,y1,x2,y2;
 86     int n;
 87     while(scanf("%d",&n) == 1) {
 88         int t = 0;
 89         for(int i = 0;i < n; i++) {
 90             scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
 91             l[t].x1 = x1;
 92             l[t].x2 = x2;
 93             l[t].y = y1;
 94             l[t].f = 1;
 95             x[t++] = x1;
 96             l[t].x1 = x1;
 97             l[t].x2 = x2;
 98             l[t].y = y2;
 99             l[t].f = -1;
100             x[t++] = x2;
101         }
102         sort(l,l+t,cmp);
103         sort(x,x+t);
104         int m = unique(x,x+t) - x;
105         build(1,0,m-1);
106         int ans = 0;
107         int last = 0;
108         for(int i = 0;i < t - 1; i++) {
109             update(1,l[i]);
110             ans += s[1].numseg * 2 * (l[i+1].y - l[i].y);
111             ans += abs(s[1].cnt - last);
112             last = s[1].cnt;
113         }
114         update(1,l[t-1]);
115         ans += abs(s[1].cnt - last);
116         printf("%d
",ans);
117     }
118     return 0;
119 }

POJ 1177 Picture(线段树 扫描线 离散化 求矩形并面积)

解题思路:

AC代码:

POJ 1177 Picture(线段树扫描线离散化求矩形并面积)