题意：给你一些矩形的左上角点的坐标和右下角点的坐标，求周长并
最显而易见的思路就是对于x轴和y轴做两次扫描线，对于负数的坐标进行离散化。每次增加的值是线段变化量的绝对值。具体写法和求面积并的差不多。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
#define lson rt << 1 , l , mid
#define rson rt << 1 | 1, mid + 1 , r
const int maxn = 10000 + 10;
int cnt[maxn << 2], len[maxn << 2], n;
struct Seg {
int x, l, r, cover;
Seg(int x, int l, int r, int cover) :x(x), l(l), r(r), cover(cover) {}
bool operator < (const Seg &seg) const {
if (x == seg.x) return cover > seg.cover;
return x < seg.x;
}
};
vector<Seg> seg;
vector<int> num;
int sx1[maxn], sy1[maxn], sx2[maxn], sy2[maxn];
void pushup(int rt, int l, int r) {
if (cnt[rt]) len[rt] = num[r + 1] - num[l];
else if (l == r) len[rt] = 0;
else len[rt] = len[rt << 1] + len[rt << 1 | 1];
}
void update(int rt, int l, int r, int ql, int qr, int Val) {
if (ql <= l && qr >= r) {
cnt[rt] += Val; pushup(rt, l, r);
}
else {
int mid = (l + r) >> 1;
if (ql <= mid) update(lson, ql, qr, Val);
if (qr > mid) update(rson, ql, qr, Val);
pushup(rt, l, r);
}
}
int GetID(int val) {
return lower_bound(num.begin(), num.end(), val) - num.begin();
}
int solve(int px1[], int py1[], int px2[], int py2[]) {
seg.clear(); num.clear();
memset(cnt, 0, sizeof(cnt));
memset(len, 0, sizeof(len));
for (int i = 0; i < n; i++) {
seg.push_back(Seg(px1[i], py1[i], py2[i], 1));
seg.push_back(Seg(px2[i], py1[i], py2[i], -1));
num.push_back(py1[i]);
num.push_back(py2[i]);
}
sort(seg.begin(), seg.end());
sort(num.begin(), num.end());
num.erase(unique(num.begin(), num.end()), num.end());
int ret = 0, msize = seg.size(), nowlen = 0, k = num.size();
for (int i = 0; i < msize; i++) {
int ql = GetID(seg[i].l), qr = GetID(seg[i].r) - 1;
update(1, 0, k - 1, ql, qr, seg[i].cover);
ret += abs(nowlen - len[1]);
nowlen = len[1];
}
return ret;
}
int main() {
while (scanf("%d", &n) != EOF) {
for (int i = 0; i < n; i++) {
scanf("%d%d%d%d", &sx1[i], &sy1[i], &sx2[i], &sy2[i]);
}
int ret = solve(sx1, sy1, sx2, sy2) + solve(sy1, sx1, sy2, sx2);
printf("%d\n", ret);
}
}
总觉得可以就做一次扫描线就可以完成统计，就是不知道应该怎么写。看了别人的blog之后发现自己还是太弱。
要统计的东西有这些，假设扫描的是y轴。
1. y轴上有多少条线段，并且如果端点重合的话就算一条。因为x轴上面有多少条线是和y轴上有多少条线段有关的，是2倍的关系。为此还要开两个数组来辅助标记，表示当前线段的左端点和右端点是否被覆盖。
2. y轴上点段的长度，这个和上面的做法统计的功能一样。
3. 当前线段被覆盖了多少次，这个也和上面的统计方法一样。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <climits>
using namespace std;
const int maxn = 2e4 + 10;
#define lson rt << 1, l, mid
#define rson rt << 1 | 1,mid + 1,r
struct Seg {
int l, r, x, cover;
Seg(int l, int r, int x, int cover) :l(l), r(r), x(x), cover(cover) {}
bool operator < (const Seg &seg) const {
if (x == seg.x) return cover > seg.cover;
return x < seg.x;
}
};
vector<Seg> seg;
int n;
bool lbound[maxn << 2], rbound[maxn << 2];
int numseg[maxn << 2], len[maxn << 2], cnt[maxn << 2];
int minval, maxval;
void pushup(int rt, int l, int r) {
int lc = rt << 1, rc = rt << 1 | 1;
if (cnt[rt]) {
lbound[rt] = rbound[rt] = true;
//因为每一条线段的长度都等于1，第l条线段起始点是l，第r条线段的结束点是r + 1,长度是r + 1 - l
len[rt] = r - l + 1;
//因为横向必定有两条边，所以为2
numseg[rt] = 2;
}
else if (l == r) {
len[rt] = numseg[rt] = lbound[rt] = rbound[rt] = 0;
}
else {
len[rt] = len[lc] + len[rc];
lbound[rt] = lbound[lc];
rbound[rt] = rbound[rc];
numseg[rt] = numseg[lc] + numseg[rc];
//如果在交点重合
if (rbound[lc] && lbound[rc]) {
numseg[rt] -= 2;
}
}
}
void update(int rt, int l, int r, int ql, int qr, int Val) {
if (ql <= l && qr >= r) {
cnt[rt] += Val;
pushup(rt, l, r);
}
else {
int mid = (l + r) >> 1;
if (ql <= mid) update(lson, ql, qr, Val);
if (qr > mid) update(rson, ql, qr, Val);
pushup(rt, l, r);
}
}
int main() {
while (scanf("%d", &n) != EOF) {
seg.clear();
minval = INT_MAX; maxval = -1;
for (int i = 1; i <= n; i++) {
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
seg.push_back(Seg(y1, y2, x1, 1));
seg.push_back(Seg(y1, y2, x2, -1));
minval = min(minval, min(y1, y2));
maxval = max(maxval, max(y1, y2));
}
sort(seg.begin(), seg.end());
int msize = seg.size(), ret = 0, last = 0;
for (int i = 0; i < msize; i++) {
if (seg[i].l < seg[i].r) update(1, minval, maxval, seg[i].l, seg[i].r - 1, seg[i].cover);
//横向的长度
if (i < msize - 1) ret += numseg[1] * (seg[i + 1].x - seg[i].x);
//纵向的长度
ret += abs(last - len[1]);
last = len[1];
}
printf("%d\n", ret);
}
return 0;
}
HDU 1828 Picture 线段树+扫描线,布布扣,bubuko.com
原文：http://www.cnblogs.com/rolight/p/3917645.html