題意：
? ? ? 給你n個(gè)矩形，問(wèn)你這n個(gè)矩形所圍成的圖形的周長(zhǎng)是多少。
思路：

? ? ? 線段樹(shù)的掃描線簡(jiǎn)單應(yīng)用，這個(gè)題目我用的方法比較笨，就是掃描兩次，上下掃描，求出多邊形的上下邊長(zhǎng)和，然后同理左右掃描，求出多邊形的左右邊長(zhǎng)的和，然后加起來(lái)就行了，還有這個(gè)題目有一個(gè)小小的提示，就是在重邊的時(shí)候記得是先加邊在刪邊。不然會(huì)多加邊（這個(gè)地方不管也能AC顯然是數(shù)據(jù)弱，不信的自己找一個(gè)簡(jiǎn)單的有重復(fù)邊的測(cè)下就知道了）。

#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; }

總結(jié)

以上是生活随笔為你收集整理的hdu1828 线段树扫描线求矩形面积的周长的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。