hdu1828 线段树扫描线求矩形面积的周长

题意：
      给你n个矩形，问你这n个矩形所围成的图形的周长是多少。
思路：

      线段树的扫描线简单应用，这个题目我用的方法比较笨，就是扫描两次，上下扫描，求出多边形的上下边长和，然后同理左右扫描，求出多边形的左右边长的和，然后加起来就行了，还有这个题目有一个小小的提示，就是在重边的时候记得是先加边在删边。不然会多加边（这个地方不管也能AC显然是数据弱，不信的自己找一个简单的有重复边的测下就知道了）。

#include<stdio.h> #include<string.h> #include<algorithm>#define lson l ,mid ,t << 1 #define rson mid ,r ,t << 1 | 1 #define N 50000 using namespace std;typedef struct {int l ,r ,h ,mk; }EDGE;typedef struct {int x1 ,x2 ,y1 ,y2; }NODE;NODE node[5500]; EDGE edge[N]; int len[N] ,cnt[N]; int tmp[11000] ,num[11000];bool camp(EDGE a ,EDGE b) {return a.h < b.h || a.h == b.h && a.mk > b.mk; }int abss(int x) {if(x < 0) return -x ;return x; }void Pushup(int l ,int r ,int t) {if(cnt[t]) len[t] = num[r] - num[l];else if(l + 1 == r) len[t] = 0;else len[t] = len[t<<1] + len[t<<1|1]; }void Update(int l ,int r ,int t ,int a ,int b ,int c) {if(a == l && b == r){cnt[t] += c;Pushup(l ,r ,t);return;}int mid = (l + r) >> 1;if(b <= mid) Update(lson ,a ,b ,c);else if(a >= mid) Update(rson ,a ,b ,c);else {Update(lson ,a ,mid ,c);Update(rson ,mid ,b ,c);}Pushup(l ,r ,t); }int search_2(int id ,int now) {int low ,up ,mid ,ans;low = 1 ,up = id;while(low <= up){mid = (low + up) >> 1;if(now <= num[mid]){ans = mid;up = mid - 1;}else low = mid + 1;}return ans; }int main () {int n ,i ,id ,sum;while(~scanf("%d" ,&n)){for(i = 1 ;i <= n ;i ++)scanf("%d %d %d %d" ,&node[i].x1 ,&node[i].y1 ,&node[i].x2 ,&node[i].y2);for(id = 0 ,i = 1 ;i <= n ;i ++){edge[++id].l = node[i].x1;edge[id].r = node[i].x2 ,edge[id].h = node[i].y1 ,edge[id].mk = 1;tmp[id] = node[i].x1;edge[++id].l = node[i].x1;edge[id].r = node[i].x2 ,edge[id].h = node[i].y2 ,edge[id].mk = -1;tmp[id] = node[i].x2;}sort(tmp + 1 ,tmp + id + 1);sort(edge + 1 ,edge + id + 1 ,camp);for(id = 0 ,i = 1 ;i <= n * 2 ;i ++)if(i == 1 || tmp[i] != tmp[i-1]) num[++id] = tmp[i];sum = 0;memset(len ,0 ,sizeof(len));memset(cnt ,0 ,sizeof(cnt));int tt = 0;for(i = 1 ;i <= n * 2 ;i ++){int l = search_2(id ,edge[i].l);int r = search_2(id ,edge[i].r);Update(1 ,id ,1 ,l ,r ,edge[i].mk);//printf("%d %d %d****\n" ,len[1] ,l ,r); sum += abs(len[1] - tt);tt = len[1];}//printf("%d\n" ,sum); for(id = 0 ,i = 1 ;i <= n ;i ++){edge[++id].l = node[i].y1;edge[id].r = node[i].y2 ,edge[id].h = node[i].x1 ,edge[id].mk = 1;tmp[id] = node[i].y1;edge[++id].l = node[i].y1;edge[id].r = node[i].y2 ,edge[id].h = node[i].x2 ,edge[id].mk = -1;tmp[id] = node[i].y2;}sort(tmp + 1 ,tmp + id + 1);sort(edge + 1 ,edge + id + 1 ,camp);for(id = 0 ,i = 1 ;i <= n * 2 ;i ++)if(i == 1 || tmp[i] != tmp[i-1]) num[++id] = tmp[i];memset(len ,0 ,sizeof(len));memset(cnt ,0 ,sizeof(cnt));tt = 0;for(i = 1 ;i <= n * 2 ;i ++){int l = search_2(id ,edge[i].l);int r = search_2(id ,edge[i].r);Update(1 ,id ,1 ,l ,r ,edge[i].mk);sum += abs(len[1] - tt);tt = len[1];}printf("%d\n" ,sum);}return 0; }

总结

以上是生活随笔为你收集整理的hdu1828 线段树扫描线求矩形面积的周长的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。