本文主要是介绍HDU 1255 覆盖的面积 线段树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：给定平面上若干矩形,求出被这些矩形覆盖过至少两次的区域的面积.
题解：和 poj1151 类似，不过要求的是面积的交，同样是先离散化然后枚举x坐标。此题更新时求y方向的“合法长度”相对于 poj1151 还有些区别, 值得比较比较。并且用lazy貌似也不合适，必须跟新至单元，因为每个节点既受父节点影响，也受子节点影响。
len[1]是覆盖一次的长度，len[2]是覆盖次数>= 2的长度。
当node[u].cover>1时，node[u].len[1] = 0
当node[u].cover=1时，node[u].len[2] = 两子树的len[1] 之和 + len[2] 之和
node[u].len[1] = node[u].rf - node[u].lf - len[2]
当node[u].cover=0时, node[u].len[1] = 两棵子树的 len[1] 之和
node[u].len[2] = 两棵子树的 len[2] 之和
#include <algorithm>
#include <iostream>
using namespace std;
#define L(x) ( x << 1 )
#define R(x) ( x << 1 | 1 )
#define N 2010
double y[N];
struct Line
{
double x, y1, y2;
int flag;
} line[N];
struct Node
{
int l, r, cover;
double lf, rf, len[3];
} node[N*3];
bool cmp ( Line a, Line b )
{
return a.x < b.x;
}
void length ( int u )
{
if ( node[u].cover > 1 )
{
node[u].len[2] = node[u].rf - node[u].lf;
node[u].len[1] = 0;
return;
}
if ( node[u].l + 1 == node[u].r ) /* 处理叶子节点 */
{
node[u].len[2] = 0;
if ( node[u].cover == 1 )
node[u].len[1] = node[u].rf - node[u].lf - node[u].len[2];
else
node[u].len[1] = 0;
return;
}
if ( node[u].cover == 1 )
{
node[u].len[2] = node[L(u)].len[1] + node[R(u)].len[1] + node[L(u)].len[2] + node[R(u)].len[2];
node[u].len[1] = node[u].rf - node[u].lf - node[u].len[2];
}
else if ( node[u].cover == 0 )
{
node[u].len[2] = node[L(u)].len[2] + node[R(u)].len[2];
node[u].len[1] = node[L(u)].len[1] + node[R(u)].len[1];
}
}
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].cover = 0;
node[u].len[1] = node[u].len[2] = 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, test, t, i;
double x1, y1, x2, y2, ans;
scanf("%d",&test);
while ( test-- )
{
scanf("%d",&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[2] * ( line[i].x - line[i-1].x );
update ( 1, line[i] );
}
printf ( "%.2lf\n", ans );
}
return 0;
}
这篇关于HDU 1255 覆盖的面积 线段树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
