Posted:

**Sun Dec 23, 2001 11:16 pm**It works with the sample input but the judges do not think we solved it. Here is how our algorithm works: We divide the city into strips from west to east. In order to do that we put the beginning and the end of each building into an array of doubles called R[] and after that we sort R. Thus any two consecutive pairs in R form a strip unless they ar equal of course. For each strip e find the buildings that is visible and put tham in an array V. After that we eliminate the duplicates from V and sort it so it displays the building in the order the problem requires.

//@begin_of_source_code

/*@JUDGE_ID: 15975FF 221 C++*/

#include<iostream.h>

#include<algo.h>

int n;

struct building{

int num;

double X;

double Y;

double W;

double D;

double H;

};

building b[110];

double R[300];

int V[300];

int lv;

int length;

bool G[110];

void InsSort(int * A, int k)

{

int i,j;

int key;

for(j = 2; j <= k; j++)

{

key = A[j];

i = j -1;

while( i > 0 && b[A

//@begin_of_source_code

/*@JUDGE_ID: 15975FF 221 C++*/

#include<iostream.h>

#include<algo.h>

int n;

struct building{

int num;

double X;

double Y;

double W;

double D;

double H;

};

building b[110];

double R[300];

int V[300];

int lv;

int length;

bool G[110];

void InsSort(int * A, int k)

{

int i,j;

int key;

for(j = 2; j <= k; j++)

{

key = A[j];

i = j -1;

while( i > 0 && b[A

*].Y > b[key].Y)*

{

A[i+1] = A{

A[i+1] = A

*;*

i = i-1;

}

A[i+1] = key;

}

}

void InsSortx(int * A, int k)

{

int i,j;

int key;

for(j = 2; j <= k; j++)

{

key = A[j];

i = j -1;

while( i > 0 && b[Ai = i-1;

}

A[i+1] = key;

}

}

void InsSortx(int * A, int k)

{

int i,j;

int key;

for(j = 2; j <= k; j++)

{

key = A[j];

i = j -1;

while( i > 0 && b[A

*].X > b[key].X)*

{

A[i+1] = A{

A[i+1] = A

*;*

i = i-1;

}

A[i+1] = key;

}

}

void ProcessRegion(double begr, double endr)

{

int k;

int N[300];

int i;

int indexofmin=0;

double min = 10000000000000;

bool changed;

int h;

for( i = 1;i <=n; i++)

Gi = i-1;

}

A[i+1] = key;

}

}

void ProcessRegion(double begr, double endr)

{

int k;

int N[300];

int i;

int indexofmin=0;

double min = 10000000000000;

bool changed;

int h;

for( i = 1;i <=n; i++)

G

*= false;*

for( i = 1; i <=n; i++)

{

if( bfor( i = 1; i <=n; i++)

{

if( b

*.X <= begr && b**.X+b**.W >=endr)*

{

G{

G

*= true;*

}

}

k = 0;

changed = false;

for( i = 1; i <=n; i++)

{

if( G}

}

k = 0;

changed = false;

for( i = 1; i <=n; i++)

{

if( G

*)*

{

N[++k] = b[i].num;

changed = true;

}

}

if (changed)

{

InsSort(N, k);

/*for( i =1; i <k; i++)

{

cout << N[i] << ' ';

}

*/

//cout << endl;

lv++;

V[lv] = N[1];

h = N[1];

for( i =2 ; i <= k; i++)

{

if(b[h].H < b[N[i]].H)

{

lv++;

V[lv] = N[i];

h = N[i];

}

}

}

else

{

lv++;

V[lv] = 0;

}

}

int main()

{

int i;

int k;

int N[300];

bool changed;

int map;

cin >> n;

while( n!=0)

{

map++;

for( i = 1; i <= n; i++)

{

cin>>b[i].X>>b[i].Y;

cin>>b[i].W>>b[i].D;

cin>>b[i].H;

b[i].num = i;

}

length = 0;

for( i = 1; i <= n; i++)

{

length++;

R[length] = b[i].X;

length++;

R[length] = b[i].X+b[i].W;

}

sort(R+1, R+length+1);

lv = 0;

for( i = 1; i <= length-1; i++)

{

if( R[i] != R[i+1])

{

ProcessRegion(R[i], R[i+1]);

}

}

/* for( i = 1; i <= lv; i++)

{

cout << V[i] << ' ';

}

cout <<endl;

*/

for( i = 1; i <=n; i++)

G[i] = false;

k = 0;

changed = false;

for( i = 1; i <=lv; i++)

{

if( !G[V[i]] && V[i]!=0)

{

N[++k] = V[i];

G[V[i]] = true;

changed = true;

}

}

InsSort(N,k);

InsSortx(N,k);

cout << "For map #" << map

<<", the visible buildings are numbered as follows:" << endl;

if(changed)

for( i =1; i <=k; i++)

{

if( i!=1)

cout << ' ';

cout << N[i];

}

cout << endl;

cin >> n;

if( n != 0)

cout << endl;

}

return 0;

}

//@end_of_source_code{

N[++k] = b[i].num;

changed = true;

}

}

if (changed)

{

InsSort(N, k);

/*for( i =1; i <k; i++)

{

cout << N[i] << ' ';

}

*/

//cout << endl;

lv++;

V[lv] = N[1];

h = N[1];

for( i =2 ; i <= k; i++)

{

if(b[h].H < b[N[i]].H)

{

lv++;

V[lv] = N[i];

h = N[i];

}

}

}

else

{

lv++;

V[lv] = 0;

}

}

int main()

{

int i;

int k;

int N[300];

bool changed;

int map;

cin >> n;

while( n!=0)

{

map++;

for( i = 1; i <= n; i++)

{

cin>>b[i].X>>b[i].Y;

cin>>b[i].W>>b[i].D;

cin>>b[i].H;

b[i].num = i;

}

length = 0;

for( i = 1; i <= n; i++)

{

length++;

R[length] = b[i].X;

length++;

R[length] = b[i].X+b[i].W;

}

sort(R+1, R+length+1);

lv = 0;

for( i = 1; i <= length-1; i++)

{

if( R[i] != R[i+1])

{

ProcessRegion(R[i], R[i+1]);

}

}

/* for( i = 1; i <= lv; i++)

{

cout << V[i] << ' ';

}

cout <<endl;

*/

for( i = 1; i <=n; i++)

G[i] = false;

k = 0;

changed = false;

for( i = 1; i <=lv; i++)

{

if( !G[V[i]] && V[i]!=0)

{

N[++k] = V[i];

G[V[i]] = true;

changed = true;

}

}

InsSort(N,k);

InsSortx(N,k);

cout << "For map #" << map

<<", the visible buildings are numbered as follows:" << endl;

if(changed)

for( i =1; i <=k; i++)

{

if( i!=1)

cout << ' ';

cout << N[i];

}

cout << endl;

cin >> n;

if( n != 0)

cout << endl;

}

return 0;

}

//@end_of_source_code