poj 1177 picture（线段树+扫描线+离散化）★

这道题目就是求这个边界的周长，首先可以讲每个矩形的左右两条边当做两条扫描线，这样如果有n个矩形，就有2*n个扫描线。

本代码中l[]数组中保存的就是每条扫描线，包含了这条线上线段的x坐标，两个端点的y坐标，以及是矩形的入边还是出边。

建一个二叉树，0 -- cnt - 1，表示有cnt个不同的y值，也就是水平线（已经去除了重复的值）。而树中的l和r标示的就是y数组的下标，当然y数组一定是先排好顺序。

有了这些内容，我们可以进行一下操作。

在建好的树上，插入一个节点，实际上就是一个线段，更新整个树，最后可以通过根节点求出y方向的周长，对于x方向的，就是两条扫描线之间的距离，不过要乘以有多少线段的数目。

下面有详细注释，希望已经说明白了：

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
/*********************************
*	l-左子树节点 r-右子树节点
*	num-子树中有多少条线段
*	len-当前结点覆盖y方向的总长度
*	cover-是否被覆盖 也就是入边+1，出边-1
*	lb-左节点是否被覆盖 rb-右结点是否被覆盖
**********************************/
struct Tnode
{
int l, r, num, len, cover;
bool lb, rb;
};
/*********************************
*	x-扫描线的横坐标
*	y1-扫描线段的下面端点的纵坐标 y2-是扫描线段上面端点的纵坐标
*	flag-标示入边还是出边
**********************************/
struct Sline
{
int x, y1, y2, flag;
};
Tnode node[20010];//segment tree
Sline l[10010];//scan line
int y[10010];//横向线的坐标值
//scan lines
保存扫描线，每个矩形两条，同时记录一共有多少y的值
void add_line(int x1, int y1, int x2, int y2, int & cnt)
{
//in line
l[cnt].x = x1;
l[cnt].y1 = y1;
l[cnt].y2 = y2;
l[cnt].flag = 1;
y[cnt ++] = y1;
//out line
l[cnt].x = x2;
l[cnt].y1 = y1;
l[cnt].y2 = y2;
l[cnt].flag = -1;
y[cnt ++] = y2;
}
//创建线段树，实际上就是一个平衡二叉树，可以画一下
void Build(int t, int l, int r)
{
node[t].l = l;
node[t].r = r;
node[t].num = 0;
if (l == r - 1)
{
return ;
}
int mid = (l + r) >> 1;
Build(2 * t, l, mid);
Build(2 * t + 1, mid, r);
}
void Updata_len(int t)
{
//cover 如果是被覆盖，也就是这段y轴上有线段覆盖着，比如只有一个矩形，第一条扫描线，肯定是覆盖了y轴上一段距离，但是过了第二条扫描线，就相当于解除了这个矩形对y轴的覆盖
if (node[t].cover > 0)
{
node[t].num = node[t].lb = node[t].rb = 1;
node[t].len = y[node[t].r] - y[node[t].l];
}
//完全没有被覆盖到测情况
else if (node[t].l == node[t].r - 1)
{
node[t].rb = node[t].lb = node[t].len = node[t].num = 0;
}
//更新父节点相应的参数
else
{
node[t].rb = node[2 * t + 1].rb;
node[t].lb = node[2 * t].lb;
node[t].len = node[2 * t].len + node[2 * t + 1].len;
node[t].num = node[2 * t].num + node[2 * t + 1].num - node[2 * t + 1].lb * node[2 * t].rb;
}
}
void Updata(int t, Sline p)
{
//找到当前扫描线段覆盖了哪些y轴上的地方
if (y[node[t].l] >= p.y1 && y[node[t].r] <= p.y2)
{
node[t].cover += p.flag;
Updata_len(t);//更新本节点两端节点是否都被覆盖，以及线段的长度，子树中分了多少段
return ;
}
//寻找自己的位置
if (node[t].l == node[t].r - 1)
{
return ;
}
int mid = (node[t].l + node[t].r) >> 1;
if (p.y1 <= y[mid])
{
Updata(2 * t, p);
}
if (p.y2 > y[mid])
{
Updata(2 * t + 1, p);
}
Updata_len(t);
}
int solve(int n, int cnt, Sline * l)
{
memset(node, 0, sizeof(node));
//build segment tree
Build(1, 0, cnt - 1);//创建线段树
int ans = 0, last = 0, lines = 0;
for (int i =0; i < n; ++ i)
{
Updata(1, l[i]);//在线段树种加入每条扫描线段
if (i >= 1)
{
ans += 2 * lines * (l[i].x - l[i - 1].x);//the length for parellel x
计算平行于x轴的长度，注意有可能不止两条，可能4条，6条，8条
}
ans += abs(node[1].len - last);//计算y方向的长度，因为线段树种节点保存的是当前覆盖的长度，所以减去以前的，就可以计算出每次变化的长度，这些变化的长度，就是每过一条扫描线，在y轴上增加的长度
last = node[1].len;//保存上次覆盖的长度
lines = node[1].num;//计算有多少段线段被覆盖，为了计算平行于x轴的乘法的因子。如果只覆盖一段，那么每两条扫描线之间就有两条相等的线段，如果被覆盖两端，那没两条扫描线之间就是4条线段，可以画一下
}
return ans;
}
//扫描线排序函数，从小到大，入边在前
bool cmp(Sline a,Sline b)
{
if( a.x == b.x ) return a.flag > b.flag;
return a.x < b.x;
}
int main()
{
int n, x1, x2, y1, y2;
while (scanf("%d", &n) != EOF)
{
if (n == 0)
{
printf("0n");
continue;
}
int cnt = 0;
for (int i = 0; i
< n; ++ i)
{
scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
add_line(x1, y1, x2, y2, cnt);
}
sort(y, y + cnt);//y值排序
sort(l, l + cnt, cmp);//扫描线排序
int t = cnt;
t = unique(y, y + cnt) - y;//去掉重复的y值
int ans = solve(cnt, t, l);
printf("%dn", ans);
}
return 0;
}

最后

以上就是激昂大米为你收集整理的poj 1177 picture（线段树+扫描线+离散化）★的全部内容，希望文章能够帮你解决poj 1177 picture（线段树+扫描线+离散化）★所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。