題目鏈接
題意
給出n個(gè)矩形，求面積并。
思路
使用掃描線，我這里離散化y軸，按照x坐標(biāo)從左往右掃過(guò)去。離散化后的y軸可以用線段樹(shù)維護(hù)整個(gè)y上面的線段總長(zhǎng)度，當(dāng)碰到掃描線的時(shí)候，就可以統(tǒng)計(jì)面積。這里要注意線段樹(shù)上結(jié)點(diǎn)維護(hù)的是線段的信息，而不是點(diǎn)的信息。
參考資料
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 10;
#define lson l, m, rt<<1
#define rson m + 1, r, rt<<1|1
struct Node {int st;double l, r, id;bool operator < (const Node &rhs) const {return id < rhs.id;}
} p[N];
double y[N], tree[N<<2];
int cnt[N<<2];void PushUp(int l, int r, int rt) {if(cnt[rt] > 0) tree[rt] = y[r+1] - y[l]; // r + 1是因?yàn)榫€段樹(shù)上結(jié)點(diǎn)是線段,映射成點(diǎn)就要+1else if(l == r) tree[rt] = 0; // 當(dāng)這個(gè)線段沒(méi)有cnt的時(shí)候就代表消失了else tree[rt] = tree[rt<<1] + tree[rt<<1|1];
}void Update(int L, int R, int w, int l, int r, int rt) {if(L <= l && r <= R) {cnt[rt] += w;PushUp(l, r, rt);return ;}int m = (l + r) >> 1;if(L <= m) Update(L, R, w, lson);if(m < R) Update(L, R, w, rson);PushUp(l, r, rt);
}int main() {int cas = 1, n;while(scanf("%d", &n), n) {int cnt = 0, m = 0;for(int i = 1; i <= n; i++) {double x1, x2, y1, y2;scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);y[++cnt] = y1, y[++cnt] = y2;p[++m] = (Node) { 1, y1, y2, x1 };p[++m] = (Node) { -1, y1, y2, x2 };}sort(y + 1, y + 1 + cnt);sort(p + 1, p + 1 + m);cnt = unique(y + 1, y + 1 + cnt) - y - 1;double ans = 0;for(int i = 1; i <= m; i++) {ans += tree[1] * (p[i].id - p[i-1].id);int L = lower_bound(y + 1, y + 1 + cnt, p[i].l) - y;int R = lower_bound(y + 1, y + 1 + cnt, p[i].r) - y - 1;// R - 1是因?yàn)榫€段樹(shù)上的結(jié)點(diǎn)是線段Update(L, R, p[i].st, 1, cnt, 1);printf("%d : %d - %d , %.2f\n", i, L, R, tree[1]);}printf("Test case #%d\n", cas++);printf("Total explored area: %.2f\n\n", ans);}return 0;
}
轉(zhuǎn)載于:https://www.cnblogs.com/fightfordream/p/7591674.html
總結(jié)
以上是生活随笔為你收集整理的HDU 1542：Atlantis（扫描线+线段树 矩形面积并）***的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
