首页 > 代码库 > poj 3277 City Horizon (线段树 扫描线 矩形面积并)

poj 3277 City Horizon (线段树 扫描线 矩形面积并)

2024-07-16 18:48:31   223人阅读

题目链接

题意： 给一些矩形，给出长和高，其中长是用区间的形式给出的，有些区间有重叠，最后求所有矩形的面积。

分析： 给的区间的范围很大，所以需要离散化，还需要把y坐标去重，不过我试了一下不去重 也不会出错，

所有的区间都能列出来，只是在查找的时候费点事。

给的矩形相当于在同一水平线上的，也就是y1坐标相当于为0，其他的就和 poj 1151 Atlantis 差不多了。

 

我写的思路是按照矩形面积并的思路写的：

但是还有另一种方法也是挺简单的，就是把给的矩形按照高从小到大排序，然后依次插入线段树，后面插入的

高会覆盖前面矮的，也就是覆盖了矩形的高，查找的时候按照00 11 22这种区间查找，只有找到h!=0的就是

当前的高，因为这表示这是后来插入的，也就是高的，然后乘上x的范围就是面积了。

  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 = 80000+10; 11 using namespace std; 12 int n; 13 double y[maxn]; 14 struct node 15 { 16     int l, r, c; 17     int cnt, lf, rf; 18 }tr[4*maxn]; 19 struct Line 20 { 21     int x, y1, y2; 22     int f; 23 }line[maxn]; 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]; 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); 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; 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, cnt; 72     LL ans; 73     int a, b, h; 74     while(~scanf("%d", &n)) 75     { 76         cnt = 1; ans = 0; 77         for(i = 0; i < n; i++) 78         { 79             scanf("%d%d%d", &a, &b, &h); 80             line[cnt].x = a; line[cnt].y1 = 0; 81             line[cnt].y2 = h; line[cnt].f = 1; 82             y[cnt++] = 0; 83             line[cnt].x = b; line[cnt].y1 = 0; 84             line[cnt].y2 = h; line[cnt].f = -1; 85             y[cnt++] = h; 86  87         } 88         sort(line+1, line+cnt, cmp); 89         sort(y+1, y+cnt); 90         int m = unique(y+1, y+cnt)-(y+1);  //对y坐标去重，不去重也没错 91         build(1, m, 1); 92  93         update(1, line[1]); 94         for(i = 2; i < cnt; i++) 95         { 96             ans += (LL)tr[1].cnt*(line[i].x-line[i-1].x); 97             update(1, line[i]); 98         } 99         printf("%I64d\n", ans);100     }101     return 0;102 }

 


联系
我们