HUD 1828 Picture 矩形周长/线段树

本文主要是介绍HUD 1828 Picture 矩形周长/线段树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：求重叠矩形的周长。
题解：枚举x区间时要注意求出， y 轴投影的线段数量。 即对应一个 x 有多少段不连续的线段，因为这关系的矩形的宽。 对 x 进行排列要记得入边在前，出边在后，否则边相交的两个矩形，就会把重边也计算在内。

#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;
#define L(x) ( x << 1 )  
#define R(x) ( x << 1 | 1 )  
#define N 20010
int y[N*2];
struct Node 
{
int l, r, len, lc, rc, cover, cnt; /* lc, rc, 表示定的被覆盖的次数 */
} node[N*4];
struct Line
{
int x, y1, y2, flag;
} line[N*2];
bool cmp ( Line a, Line b )
{
if ( a.x != b.x )
return a.x < b.x;
return a.flag > b.flag; /* 当 x 相同时应当是入边在前, 画两个矩形分析分析 */
}
void y_update ( int u )
{
if ( node[u].cover > 0 )
node[u].len = y[node[u].r] - y[node[u].l];
else if ( node[u].l + 1 == node[u].r )
node[u].len = 0;
else
node[u].len = node[L(u)].len + node[R(u)].len;
if ( node[u].cover > 0 )
node[u].cnt = 1; /* cnt 记录投影到 y 轴上的线段数（ 即不连续的段数） */
else
{
node[u].cnt = node[L(u)].cnt + node[R(u)].cnt;
if ( node[R(u)].lc != 0 && node[L(u)].rc != 0 )  
/*左子树的右端点如果跟右子树的左端点都被覆盖了,说明在整个区间里，有一个区间横跨左右子树，但被重复计算了，所以要减去1 */
node[u].cnt--;
}
}
void build( int u, int l, int r )
{
node[u].l = l;   
node[u].r = r;
node[u].cnt = 0;
node[u].len = node[u].cover = 0;
node[u].lc = node[u].rc = 0;
if ( l + 1 == r ) return;
int mid = ( l + r ) >> 1;
build ( L(u), l, mid );
build ( R(u), mid, r );
}
void update ( int u, Line e )
{  
if ( e.y1 == y[node[u].l] )
node[u].lc += e.flag;
if ( e.y2 == y[node[u].r] )
node[u].rc += e.flag;
if ( e.y1 == y[node[u].l] && e.y2 == y[node[u].r] )
{
node[u].cover += e.flag; 
y_update ( u );
return;
}
if ( e.y1 >= y[node[R(u)].l] )
update ( R(u), e );
else if ( e.y2 <= y[node[L(u)].r] )
update ( L(u), e );
else
{
Line temp1 = e;
Line temp2 = e;
temp1.y2 = y[node[L(u)].r];
temp2.y1 = y[node[R(u)].l];
update ( L(u), temp1 );
update ( R(u), temp2 );
}
y_update ( u );
}
int main()
{
//freopen ( "a.txt", "r", stdin );
int n, i, k, x1, y1, x2, y2;
while ( scanf("%d",&n) != EOF )
{
for ( i = k = 1; i <= n; i++, k++ )
{
scanf("%d %d %d %d", &x1, &y1, &x2, &y2 );
line[k].x = x1;
line[k].y1 = y1;
line[k].y2 = y2;
line[k].flag = 1;
y[k] = y1;
k++;
line[k].x = x2;
line[k].y1 = y1;
line[k].y2 = y2;
line[k].flag = -1;
y[k] = y2;
}
sort ( line+1, line+k, cmp );
sort ( y+1, y+k );
build ( 1, 1, k-1 );
update ( 1, line[1] );
int ans = node[1].len;
int temp = node[1].len;
int tcnt = node[1].cnt;
for ( i = 2; i < k; i++ )
{
update ( 1, line[i] );
ans += abs ( node[1].len - temp );
ans += 2 * ( line[i].x - line[i-1].x ) * tcnt;
temp = node[1].len;
tcnt = node[1].cnt;
}
printf ( "%d\n", ans );
}
return 0;
}

这篇关于HUD 1828 Picture 矩形周长/线段树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---