hdu 1828(离散化+扫描线)

57 阅读 0 评论 38 点赞

我是靠谱客的博主坚强糖豆，最近开发中收集的这篇文章主要介绍hdu 1828(离散化+扫描线)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意：给出n个矩形的左下角坐标和右上角坐标，求所有矩形的最后的并的周长。
题解：上一题是求面积，这一题是求周长，还是要用线段树维护此时每个区间覆盖的长度，还要用线段树维护覆盖了几段，也就是不相邻的线段的数量，这样从一条边扫描到另一条边的纵坐标变化×2×段数就是竖直的矩形周长，然后横向的矩形周长只要用一个变量记录上一次的总区间覆盖长度和这一次的总区间覆盖长度的差值，累加到解里就可以了。注意线段树还要维护左右端点是否被覆盖，因为区间合并的时候如果左子区间的右端点和右子区间的左端点都被覆盖，段数就多加了一条，要减掉。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
const int N = 10005;
struct Line {
int flag;
int lx, rx, h;
Line(int a, int b, int c, int d):lx(a), rx(b), h(c), flag(d) {}
bool operator < (const Line &a) const { return h < a.h; }
};
int n, flag[N << 2], tree[N << 2], num[N << 2], lcov[N << 2], rcov[N << 2];
vector<int> a;
vector<Line> line;
map<int, int> mp;
void pushup(int k, int left, int right) {
if (flag[k]) {
lcov[k] = rcov[k] = num[k] = 1;
tree[k] = a[right] - a[left];
}
else if (left + 1 == right)
tree[k] = num[k] = lcov[k] = rcov[k] = 0;
else {
tree[k] = tree[k * 2] + tree[k * 2 + 1];
num[k] = num[k * 2] + num[k * 2 + 1];
if (rcov[k * 2] && lcov[k * 2 + 1])
num[k]--;
lcov[k] = lcov[k * 2];
rcov[k] = rcov[k * 2 + 1];
}
}
void modify(int k, int left, int right, int l, int r, int v) {
if (l <= left && right <= r) {
flag[k] += v;
num[k] += v;
if (flag[k]) {
lcov[k] = rcov[k] = 1;
tree[k] = a[right] - a[left];
}
else lcov[k] = rcov[k] = tree[k] = 0;
pushup(k, left, right);
return;
}
int mid = (left + right) / 2;
if (l < mid)
modify(k * 2, left, mid, l, r, v);
if (r > mid)
modify(k * 2 + 1, mid, right, l, r, v);
pushup(k, left, right);
}
int main() {
while (scanf("%d", &n) == 1) {
a.clear(), line.clear(), mp.clear();
memset(flag, 0, sizeof(flag));
memset(tree, 0, sizeof(tree));
memset(num, 0, sizeof(num));
memset(lcov, 0, sizeof(lcov));
memset(rcov, 0, sizeof(rcov));
int x1, y1, x2, y2;
for (int i = 1; i <= n; i++) {
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
line.push_back(Line(x1, x2, y1, 1));
line.push_back(Line(x1, x2, y2, -1));
a.push_back(x1);
a.push_back(x2);
}
sort(line.begin(), line.end());
sort(a.begin(), a.end());
a.erase(unique(a.begin(), a.end()), a.end());
int sz = a.size(), sz2 = line.size();
for (int i = 0; i < sz; i++)
mp[a[i]] = i;
int res = 0, temp = 0;
for (int i = 0; i < sz2; i++) {
if (i != 0)
res += 2 * num[1] * (line[i].h - line[i - 1].h);
modify(1, 0, sz - 1, mp[line[i].lx], mp[line[i].rx], line[i].flag);
res += abs(tree[1] - temp);
temp = tree[1];
}
printf("%dn", res);
}
return 0;
}