洛谷題目鏈接:[USACO5.5]矩形周長Picture

題目背景

墻上貼著許多形狀相同的海報、照片。它們的邊都是水平和垂直的。每個矩形圖片可能部分或全部的覆蓋了其他圖片。所有矩形合并后的邊長稱為周長。

題目描述

編寫一個程序計算周長。

如圖1所示7個矩形。

如圖2所示，所有矩形的邊界。所有矩形頂點的坐標(biāo)都是整數(shù)。

輸入輸出格式

輸入格式：

輸入文件的第一行是一個整數(shù)N（0<=N<5000），表示有多少個矩形。接下來N行給出了每一個矩形左下角坐標(biāo)和右上角坐標(biāo)（所有坐標(biāo)的數(shù)值范圍都在-10000到10000之間）。

輸出格式：

輸出文件只有一個正整數(shù)，表示所有矩形的周長。

輸入輸出樣例

輸入樣例#1：

7
-15 0 5 10
-5 8 20 25
15 -4 24 14
0 -6 16 4
2 15 10 22
30 10 36 20
34 0 40 16

輸出樣例#1：

228

題意: 給出一堆矩形,要你計算周長.

題解: 類似一堆矩形要你求某些信息的,基本上都可以用掃描線來做.

首先還是將矩形拆成線按照坐標(biāo)排序,然后我們需要在線段樹中記錄幾個變量:\(cov\)表示這個區(qū)間被覆蓋的長度,\(sum\)表示這個區(qū)間的和(我們會在每次加入線段的時候給區(qū)間加上一個權(quán)值,會直接修改在\(sum\)變量里,但是\(sum\)標(biāo)記不會下放).

接下來考慮如何寫\(push\_up\)函數(shù).首先判斷一個節(jié)點被覆蓋的長度先要看這個節(jié)點的\(sum\)是否有值,因為任何加入/刪除線段的操作都會對\(sum\)進行修改,那么如果\(sum\)有值,顯然\(cov=r-l+1\)(我這里使用的是閉區(qū)間).

如果\(sum\)的值為\(0\)呢?這時候我們需要判斷這個節(jié)點是否為葉子節(jié)點,如果是葉子節(jié)點則\(cov=0\),否則\(cov=cov_{lson}+cov_{rson}\),判斷是否為葉子的原因是防止越界.

然后查詢的時候直接返回\(1\)節(jié)點的\(cov\)值就是整個區(qū)間內(nèi)的覆蓋數(shù)了.

那么答案如何統(tǒng)計呢?我這里是將\(x,y\)軸分兩次求的,實際上可以一次做完,但是我自己\(yy\)的時候沒想到這么多...

其實我們只需要每次插入一條線段,然后加入這次插入后\(cov\)的變化量的絕對值就可以了.

不懂可以看下代碼.

#include<bits/stdc++.h> #define ll(x) (x << 1) #define rr(x) (x << 1 | 1) using namespace std; const int N = 10000+5;int n, cnt[2], ans = 0;struct line{ int x, l, r, v; }a[2][N*2];bool cmp(line a, line b){ return a.x != b.x ? a.x < b.x : a.v > b.v; }struct SegmentTree{ int l, r, sum, cov; }t[2][N*8];void up(int x, int k){if(t[k][x].sum) t[k][x].cov = t[k][x].r-t[k][x].l+1;else if(t[k][x].l == t[k][x].r) t[k][x].cov = 0;else t[k][x].cov = t[k][ll(x)].cov+t[k][rr(x)].cov; }void build(int x, int l, int r, int k){t[k][x].l = l, t[k][x].r = r, t[k][x].sum = t[k][x].cov = 0;if(l == r) return; int mid = (l+r>>1);build(ll(x), l, mid, k), build(rr(x), mid+1, r, k); }void update(int x, int l, int r, int val, int k){if(l <= t[k][x].l && t[k][x].r <= r){t[k][x].sum += val, up(x, k); return;}int mid = (t[k][x].l+t[k][x].r>>1);if(l <= mid) update(ll(x), l, r, val, k);if(mid < r) update(rr(x), l, r, val, k); up(x, k); }void solve(int k){int last = 0, pos = 1; build(1, 1, N*2, k);sort(a[k]+1, a[k]+cnt[k]+1, cmp);for(pos = 1; pos <= cnt[k]; pos++){update(1, a[k][pos].l, a[k][pos].r-1, a[k][pos].v, k); //int add = abs(t[k][1].cov-last);ans += abs(t[k][1].cov-last), last = t[k][1].cov;} }int main(){ios::sync_with_stdio(false);int a1, b1, a2, b2; cin >> n;for(int i = 1; i <= n; i++){cin >> a1 >> b1 >> a2 >> b2;a1 += N, b1 += N, a2 += N, b2 += N;a[0][++cnt[0]] = (line){ a1, b1, b2, 1 };a[0][++cnt[0]] = (line){ a2, b1, b2, -1 };a[1][++cnt[1]] = (line){ b1, a1, a2, 1 };a[1][++cnt[1]] = (line){ b2, a1, a2, -1 };}solve(0), solve(1);cout << ans << endl;return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/BCOI/p/10423238.html

總結(jié)

以上是生活随笔為你收集整理的[洛谷P1856] [USACO5.5]矩形周长Picture的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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