题意：求n个矩形周长的并（0 <= number of rectangles < 5000，坐标范围：[-10000,10000] ）。
题目链接：http://poj.org/problem?id=1177
——>>思路与poj1151矩形面积的并类似，提取出所有矩形的所有纵向边作为扫描线，从左往右扫描，每处理一条扫描线时，下一条扫描线与当前扫描线的距离乘上当前已覆盖纵向边所包含的连续线段数再乘上2是一个部分周长（横的周长），当前已覆盖纵向边的长度与上一次扫描时覆盖纵向边的长度的差的绝对值则是此次扫描增加的纵向周长，将这些部分周长累加起来就是n个矩形周长的并。。
而当前覆盖到纵向边长度可通过线段树来维护。。空间上则要求先对所有点的纵坐标进行离散化。。
总时间复杂度为O(nlogn)。。
陈宏的论文题。。线段树的经典。。
#include <cstdio>
#include <algorithm>using namespace std;#define lc (o<<1)
#define rc ((o<<1) + 1)const int MAXN = 5000;int y[MAXN<<1], cnt;struct ScanLine {int x;int y1, y2;bool is_left;bool operator < (const ScanLine& e) const {return x < e.x;}
} scanlines[MAXN<<1];struct Node {int L, R;int len;int segs;int cover;int lcover, rcover;
} nodes[MAXN << 3];void build(int o, int L, int R) {nodes[o].L = L;nodes[o].R = R;nodes[o].len = 0;nodes[o].segs = 0;nodes[o].cover = 0;nodes[o].lcover = 0;nodes[o].rcover = 0;if(L + 1 == R) return;int M = (L + R) >> 1;build(lc, L, M);build(rc, M, R);
}int point_to(int x) { //离散化后找映射值return lower_bound(y, y + cnt, x) - y;
}void maintain_len(int o) { //维护区间覆盖长度if(nodes[o].cover > 0) {nodes[o].len = y[nodes[o].R] - y[nodes[o].L];}else if(nodes[o].L + 1 == nodes[o].R) {nodes[o].len = 0;}else {nodes[o].len = nodes[lc].len + nodes[rc].len;}}void maintain_segs(int o) { //维护区间连续线段数if(nodes[o].cover > 0) {nodes[o].segs = 1;nodes[o].lcover = nodes[o].rcover = 1;}else if(nodes[o].L + 1 == nodes[o].R) {nodes[o].segs = 0;nodes[o].lcover = 0;nodes[o].rcover = 0;}else {nodes[o].segs = nodes[lc].segs + nodes[rc].segs - nodes[lc].rcover*nodes[rc].lcover;nodes[o].lcover = nodes[lc].lcover;nodes[o].rcover = nodes[rc].rcover;}
}void my_insert(int o, int ql, int qr) { //线段树插入if(ql <= nodes[o].L && nodes[o].R <= qr) {nodes[o].cover++;maintain_len(o);maintain_segs(o);return;}int M = (nodes[o].L + nodes[o].R) >> 1;if(ql < M) my_insert(lc, ql, qr);if(qr > M) my_insert(rc, ql, qr);maintain_len(o);maintain_segs(o);
}void my_delete(int o, int ql, int qr) { //线段树删除if(ql <= nodes[o].L && nodes[o].R <= qr) {nodes[o].cover--;maintain_len(o);maintain_segs(o);return;}int M = (nodes[o].L + nodes[o].R) >> 1;if(ql < M) my_delete(lc, ql, qr);if(qr > M) my_delete(rc, ql, qr);maintain_len(o);maintain_segs(o);
}int main()
{int n, x1, y1, x2, y2;while(scanf("%d", &n) == 1) {for(int i = 0; i < n; i++) {scanf("%d%d%d%d", &x1, &y1, &x2, &y2);scanlines[i<<1].x = x1;scanlines[i<<1].y1 = y1;scanlines[i<<1].y2 = y2;scanlines[i<<1].is_left = true;scanlines[(i<<1)+1].x = x2;scanlines[(i<<1)+1].y1 = y1;scanlines[(i<<1)+1].y2 = y2;scanlines[(i<<1)+1].is_left = false;y[i<<1] = y1;y[(i<<1)+1] = y2;}sort(y, y + 2*n); //离散化cnt = unique(y, y + 2*n) - y;build(1, 0, 2*n-1);sort(scanlines, scanlines + 2*n);int perimeter = 0; //周长int last_len = 0; //上一次整棵线段树已覆盖的长度for(int i = 0; i < 2*n-1; i++) { //2n条扫描线依次进行扫描if(scanlines[i].is_left) { //入边插入my_insert(1, point_to(scanlines[i].y1), point_to(scanlines[i].y2));}else { //出边删除my_delete(1, point_to(scanlines[i].y1), point_to(scanlines[i].y2));}perimeter += (scanlines[i+1].x - scanlines[i].x) * 2 * nodes[1].segs; //加横边perimeter += abs(nodes[1].len - last_len); //加竖边last_len = nodes[1].len;}my_delete(1, point_to(scanlines[2*n-1].y1), point_to(scanlines[2*n-1].y2));perimeter += abs(nodes[1].len - last_len);printf("%d\n", perimeter);}return 0;
}