221 - Urban Elevations

[bigredteam2000]

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].Y > b[key].Y)
{
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[A].X > b[key].X)
{
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++)
G = false;

for( i = 1; i <=n; i++)
{
if( b.X <= begr && b.X+b.W >=endr)
{
G = true;
}
}
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

[Gatis]

Hi, all,

I've been trying to solve the 221 problem. I Think I can solve it use a simple algorithm, as follow:

[cpp]
visitBuild(b, xMin, xMax, height) {
if (xMin >= xMain) return;
if (b.front intersects [xMin; xMax]) && (b.height > heigth) {
b.visited = true;[/code]
//There are 3 cases.
// here only when the build is fully between [xMin; xMax].[/i]
visitBuild(b.next, xMin, b.left, height);
visitBuild(b.next, b.left, b.right, b.height);
visitBuild(b.next, b.right, xMax, height);
} else {
visitBuild(b.next, xMin, xMax, height);
}
}

Main() {
readData();
sortData(bySouth);
visitBuild(firstBuild, xMin, xMax, 0);
sortData(byWest);
printVisitedBuilds();
}
[/cpp]

It passes by the sample output, but I only get WA. Does anyone know why?

Thanks,
[]'s Gatis

[Gatis]

Hi, again,

I discovered... the problem permits 0 width builds... :|

[]'s
Gatis

[Caesum]

Such a building would not be visible surely ?

For this program, a building is considered visible whenever the part of its southern face that appears in the elevation has strictly positive area.

[Caesum]

i hate problems where the description is wrong, grr how can so many people pass them ?

[StatujaLeha]

Hi all!

I hope for your help. I got WA many times, but not understand where a mistake in my algorithm. Because of it I ask you to give me a test input and an output to check up my program.

Thank you.

[locke]

I keep getting PE with 221 (Urban Elevations). Here is a sample of the output:

Code: Select all

For map #1, the visible buildings are numbered as follows:
5 9 4 3 10 2 1 14

For map #2, the visible buildings are numbered as follows:
1

For map #3, the visible buildings are numbered as follows:
1 2 3

I've tried all the silly things like adding a new line at the end, to no avail. Anyone know the gotcha on this?

By the way, why does the [ CODE ] tag add a space to each line? (that's NOT part of my output).

thanks

[locke]

Ah, finally got Accepted. The problem description is wrong:

One blank line must separate output from consecutive input records.

There needs to be NO blank line separating cases. Ugh... someone fix it please .

[Carlos]

solved.

[andysoft]

Well, why do I get AC PE then? (I tried many variants...)

Code: Select all

#include <cstdlib>
#include <iostream>

using namespace std;

int main(int argc, char* argv[]) {
//CODE (no connection with I/O)

	cin >> n;
	ci = 0;

	while (n != 0) {

//CODE (no connection with I/O)
		cout <<"For map #"<<ci<<", the visible buildings are numbered as follows:"<<endl;

		for (i=1; i < k; i++)
			cout << na[i] << " ";
		cout << na[k] << endl;

		cin >> n;
	}

	return 0;
}

Thanx for help!

[andysoft]

Okay, I finally got AC.
You need to print blank line only between cases. And no blank lines after the last case.