HDU_1828 Picture線分ツリー
4428 ワード
http://acm.hdu.edu.cn/showproblem.php?pid=1828
タイトル:
N個の長方形をあげて、その輪郭線の周長を求めます.
考え方:
線分樹この問題は実は矩形を求めて面積が似ているが、両者には一つの場所が異なる.矩形の面積を求める場合、矩形ごとにX軸に投影し、走査線で各メタ線分区間内、X軸方向の有効長さを求め、その後(p[i+1].h-p[i].h)*sum[1]がそのメタ線分区間内の有効面積であり、そのsum[1]は区間全体の有効線分の長さを表す.これにより矩形の周長を求める方法が容易に考えられ、同様に矩形をX軸に投影することができ、周長はX方向の周長とY方法の周長に分けられ、まずX方向の周長を求め、X方向の周長はsum[1]である. - Lastは、lastが前回求めたsum[1]の値であり、この値がこのメタセグメント区間内のX方向のセグメント長である.このようなやり方の正しさは,我々には考えられる.これによりX方向の線分長が求められ、次にY方向の線分長が求められる.ここでは線分ツリーのノード内に情報を追加することができる.この区間に含まれる線分の本数をnum[]配列で記録することで、最後のY方向の線分長がnum[1]*(p[i+1].h-p[i].h)である.これも直感的な想像で見ることができます.ここまで来れば本題は解決できる.本題の線分ツリーのノードは、座標が引かれた点ではなく、座標軸上の区間であり、一般的な線分ツリーとは異なる場所です.
コード:
タイトル:
N個の長方形をあげて、その輪郭線の周長を求めます.
考え方:
線分樹この問題は実は矩形を求めて面積が似ているが、両者には一つの場所が異なる.矩形の面積を求める場合、矩形ごとにX軸に投影し、走査線で各メタ線分区間内、X軸方向の有効長さを求め、その後(p[i+1].h-p[i].h)*sum[1]がそのメタ線分区間内の有効面積であり、そのsum[1]は区間全体の有効線分の長さを表す.これにより矩形の周長を求める方法が容易に考えられ、同様に矩形をX軸に投影することができ、周長はX方向の周長とY方法の周長に分けられ、まずX方向の周長を求め、X方向の周長はsum[1]である. - Lastは、lastが前回求めたsum[1]の値であり、この値がこのメタセグメント区間内のX方向のセグメント長である.このようなやり方の正しさは,我々には考えられる.これによりX方向の線分長が求められ、次にY方向の線分長が求められる.ここでは線分ツリーのノード内に情報を追加することができる.この区間に含まれる線分の本数をnum[]配列で記録することで、最後のY方向の線分長がnum[1]*(p[i+1].h-p[i].h)である.これも直感的な想像で見ることができます.ここまで来れば本題は解決できる.本題の線分ツリーのノードは、座標が引かれた点ではなく、座標軸上の区間であり、一般的な線分ツリーとは異なる場所です.
コード:
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<stdlib.h>
#include<math.h>
using namespace std ;
#define LL(a) ( (a)<<1 )
#define RR(a) ( (a)<<1|1 )
#define MIN(a , b) ( (a) > (b) ? (b) : (a) )
#define MAX(a , b) ( (a) > (b) ? (a) : (b) )
const int MAXN = 20010 ;
int N ;
struct Seg{
int l , r , h , s;
Seg(){}
Seg(int a, int b ,int c , int d)
:l(a) , r(b) , h(c) , s(d) {}
bool operator < ( const Seg& cmp ) const {
return h < cmp.h ;
}
}p[MAXN] ;
int col[MAXN<<2] ;
int set[MAXN<<2] ;
int sum[MAXN<<2] ;
int num[MAXN<<2] ;
bool cl[MAXN<<2] ;
bool cr[MAXN<<2] ;
void build(int l ,int r , int idx){
col[idx] = set[idx] = sum[idx] = num[idx] = 0 ;
cl[idx] = cr[idx] = 0 ;
if(l == r) return ;
int mid = (l + r) >> 1 ;
build(l , mid, LL(idx) ) ;
build(mid+1,r , RR(idx) ) ;
}
void down(int l ,int r, int idx){
int mid = (l + r) >> 1 ;
if( set[idx] != 0 ){
set[ LL(idx) ] += set[idx] ;
set[ RR(idx) ] += set[idx] ;
col[ LL(idx) ] += set[idx] ;
col[ RR(idx) ] += set[idx] ;
if( col[ LL(idx) ] > 0 ){
sum[ LL(idx) ] = mid - l + 1 ;
num[ LL(idx) ] = 1 ;
cl[ LL(idx) ] = cr[ LL(idx) ] = 1 ;
}
else{
sum[ LL(idx) ] = num[ LL(idx) ] = 0 ;
cl[ LL(idx) ] = cr[ LL(idx) ] = 0 ;
}
if( col[ RR(idx) ] > 0 ){
sum[ RR(idx) ] = r - mid ;
num[ RR(idx) ] = 1 ;
cl[ RR(idx) ] = cr[ RR(idx) ] = 1 ;
}
else{
sum[ RR(idx) ] = num[ RR(idx) ] = 0 ;
cl[ RR(idx) ] = cr[ RR(idx) ] = 0 ;
}
set[idx] = 0 ;
}
}
void up(int l, int r, int idx ){
int ls = LL(idx) , rs = RR(idx) ;
if( col[ls] == col[rs] ) col[idx] = col[ls] ;
else col[idx] = -1 ;
cl[idx] = cl[ls] ;
cr[idx] = cr[rs] ;
sum[idx] = sum[ ls ] + sum[ rs ] ;
num[idx] = num[ls] + num[rs] ;
if( cr[ls] && cl[rs] ) num[idx] -- ;
}
void update(int l ,int r, int idx, int a, int b, int v){
if(l==a && b==r && col[idx] != -1 ){
col[idx] += v ;
set[idx] += v ;
if( col[idx] > 0 ){
num[idx] = 1 ; sum[idx] = r-l+ 1 ;
cl[idx] = cr[idx] = 1 ;
}
else{
num[idx] = sum[idx] = 0 ;
cl[idx] = cr[idx] = 0;
}
return ;
}
down(l ,r , idx) ;
int mid = (l + r) >> 1 ;
if( b<=mid ) update(l , mid , LL(idx) , a , b , v);
else if( mid<a ) update(mid+1, r, RR(idx) , a, b, v );
else{
update(l,mid,LL(idx) ,a, mid, v ) ;
update(mid+1, r, RR(idx) , mid+1, b , v );
}
up(l, r, idx );
}
int main(){
int a, b, c, d ;
while( scanf("%d",&N) == 1){
int m = 0 ;
int L ,R ;
L = 1000000 ; R = -1000000 ;
for(int i=0 ; i<N ; i++){
scanf("%d %d %d %d",&a,&b,&c,&d);
p[m++] = Seg(a ,c , b , 1 );
p[m++] = Seg(a, c , d , -1);
L = MIN( L , a );
R = MAX( R , c );
}
sort(p, p+m);
int ans = 0 , last = 0 ;
build(L,R-1,1) ;
for(int i=0;i<m;i++){
int s = p[i].l , e =p[i].r -1 ;
if( s<=e )
update(L, R, 1, s , e , p[i].s );
ans += abs( sum[1] - last ) ; //x
last = sum[1] ;
ans += num[1]*( p[i+1].h - p[i].h ) * 2 ;
}
printf("%d
",ans);
}
return 0 ;
}