本文主要是介绍POJ 1151 Atlantis 线段树/矩形面积并，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：求矩形的面积并。
题解：
求矩形的并，由于矩形的位置可以多变，因此矩形的面积一下子不好求
这个时候，可以采用“分割”的思想，即把整块的矩形面积分割成几个小矩形的面积，然后求和就行了
这里我们可以这样做，把每个矩形投影到 y 坐标轴上来
然后我们可以枚举矩形的 x 坐标，然后检测当前相邻 x 坐标上 y 方向的合法长度，两种相乘就是面积
然后关键就是如何用线段树来维护那个 “合法长度”
可以这样来搞
线段树的节点这样定义
struct node { int left,right,cov; double len; }
cov 表示当前节点区间是否被覆盖，len 是当前区间的合法长度
然后我们通过“扫描线”的方法来进行扫描
枚举 x 的竖边，矩形的左边那条竖边就是入边，右边那条就是出边了
然后把所有这些竖边按照 x 坐标递增排序，每次进行插入操作
由于坐标不一定为整数，因此需要进行离散化处理
每次插入时如果当前区间被完全覆盖，那么就要对 cov 域进行更新
入边 +1 出边 -1
更新完毕后判断当前节点的 cov 域是否大于 0
如果大于 0，那么当前节点的 len 域就是节点所覆盖的区间
否则
如果是叶子节点，则 len=0
如果内部节点，则 len=左右儿子的 len 之和
以上转自http://hi.baidu.com/legend_ni/blog/item/106e9f8a34ff9b04b21bba71
看的晕晕的，其实只需要自己画个图分析分析便可理解。
#include <algorithm>
#include <iostream>
using namespace std;
#define L(x) ( x << 1 )
#define R(x) ( x << 1 | 1 )
double y[1000];
struct Line
{
double x, y1, y2;
int flag;
} line[300];
struct Node
{
int l, r, cover;
double lf, rf, len;
} node[1000];
bool cmp ( Line a, Line b )
{
return a.x < b.x;
}
void length ( int u )
{
if ( node[u].cover > 0 )
{
node[u].len = node[u].rf - node[u].lf;
return;
}
else if ( node[u].l + 1 == node[u].r )
node[u].len = 0; /* 叶子节点，len 为 0 */
else
node[u].len = node[L(u)].len + node[R(u)].len;
}
void build ( int u, int l, int r )
{
node[u].l = l; node[u].r = r;
node[u].lf = y[l]; node[u].rf = y[r];
node[u].len = node[u].cover = 0;
if ( l + 1 == r ) return;
int mid = ( l + r ) / 2;
build ( L(u), l, mid );
build ( R(u), mid, r );
}
void update ( int u, Line e )
{
if ( e.y1 == node[u].lf && e.y2 == node[u].rf )
{
node[u].cover += e.flag;
length ( u );
return;
}
if ( e.y1 >= node[R(u)].lf )
update ( R(u), e );
else if ( e.y2 <= node[L(u)].rf )
update ( L(u), e );
else
{
Line temp = e;
temp.y2 = node[L(u)].rf;
update ( L(u), temp );
temp = e;
temp.y1 = node[R(u)].lf;
update ( R(u), temp );
}
length ( u );
}
int main()
{
//freopen("a.txt","r",stdin);
int n, t, i, Case = 0;
double x1, y1, x2, y2, ans;
while ( scanf("%d",&n) && n )
{
for ( i = t = 1; i <= n; i++, t++ )
{
scanf("%lf%lf%lf%lf",&x1, &y1, &x2, &y2 );
line[t].x = x1;
line[t].y1 = y1;
line[t].y2 = y2;
line[t].flag = 1;
y[t] = y1;
t++;
line[t].x = x2;
line[t].y1 = y1;
line[t].y2 = y2;
line[t].flag = -1;
y[t] = y2;
}
sort ( line + 1, line + t, cmp );
sort ( y + 1, y + t );
build ( 1, 1, t-1 );
update ( 1, line[1] );
ans = 0;
for ( i = 2; i < t; i++ )
{
ans += node[1].len * ( line[i].x - line[i-1].x );
update ( 1, line[i] );
}
printf ( "Test case #%d\n", ++Case );
printf ( "Total explored area: %.2lf\n\n", ans );
}
return 0;
}
这篇关于POJ 1151 Atlantis 线段树/矩形面积并的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
