poj - 1177 - Picture（离线化+扫描线+线段树）

54 阅读 0 评论 36 点赞

我是靠谱客的博主多情丝袜，最近开发中收集的这篇文章主要介绍poj - 1177 - Picture（离线化+扫描线+线段树），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意：求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("%dn", perimeter);
}
return 0;
}