Friday, March 1, 2013

sky line problem


struct BDL
{
int x1;
int y;
int x2;
BDL(int x1_,int y_,int x2_){x1=x1_;y=y_;x2=x2_;}
};
struct INTVL
{
int x;
int h;
};

struct ltstr2
{
bool operator()(INTVL l,INTVL r)const
{
return l.x<r.x;
}
};

void SkyLine(vector<BDL> buildings)
{
set<INTVL,ltstr2> bdls;
INTVL intvl;
intvl.x=-INT_MAX;
intvl.h=0;
bdls.insert(intvl);
for(int i=0;i<buildings.size();i++)
{
BDL bdl=buildings[i];
int x1=bdl.x1,x2=bdl.x2,h1=bdl.y;
INTVL int1,int2;
int1.x=x1;
int2.x=x2;
set<INTVL,ltstr2>::iterator iter1=bdls.upper_bound(int1);
iter1--;
set<INTVL,ltstr2>::iterator iter2=bdls.lower_bound(int2);
set<INTVL,ltstr2> bdls2=bdls;
for(set<INTVL,ltstr2>::iterator iter=iter1;iter!=iter2;iter++)
{
x1=bdl.x1;x2=bdl.x2;h1=bdl.y;
set<INTVL,ltstr2>::iterator iter3=iter;
iter3++;
int x3,x4;
INTVL intvl=*iter;
x3=intvl.x,x4;
if(iter3==bdls.end())x4=INT_MAX;
else x4=(*iter3).x;
int h2=(*iter).h;
if(x1<x3)x1=x3;
if(x2>x4)x2=x4;
if(h2<h1)
{
INTVL nIntvl;
nIntvl.x=(*iter).x;
nIntvl.h=(*iter).h;
if(x3==x1)
bdls2.erase(nIntvl);
nIntvl.x=x1;
nIntvl.h=h1;
bdls2.insert(nIntvl);
if(x4>x2)
{
INTVL nIntvl;
nIntvl.x=x2;
nIntvl.h=h2;
bdls2.insert(nIntvl);
}
}

}
bdls=bdls2;
}
int lastH=0;
for(set<INTVL,ltstr2>::iterator iter=bdls.begin();iter!=bdls.end();iter++)
{
if((*iter).h==lastH)continue;
cout<<(*iter).x<<" "<<(*iter).h<<endl;
lastH=(*iter).h;
}
}

Logic is important. Keep clear of the logic when writing code. dont rush.

No comments:

Post a Comment