221 - Urban Elevations
Moderator: Board moderators
-
- New poster
- Posts: 11
- Joined: Sat Nov 17, 2001 2:00 am
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
//@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
P221
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
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
Re: P221
Hi, again,
I discovered... the problem permits 0 width builds... :|
[]'s
Gatis
I discovered... the problem permits 0 width builds... :|
[]'s
Gatis
-
- Learning poster
- Posts: 91
- Joined: Tue May 31, 2005 2:01 pm
- Location: Russia
221 - Urban Elevations
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.
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.
221 - PE!!
I keep getting PE with 221 (Urban Elevations). Here is a sample of the output:
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
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
By the way, why does the [ CODE ] tag add a space to each line? (that's NOT part of my output).
thanks
-
- Experienced poster
- Posts: 109
- Joined: Sat Jun 23, 2007 9:53 pm
- Location: Brest, BELARUS
- Contact:
Well, why do I get AC PE then? (I tried many variants...)
Thanx for help!
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;
}
Now I lay me down to sleep...
my profile
my profile
-
- Experienced poster
- Posts: 109
- Joined: Sat Jun 23, 2007 9:53 pm
- Location: Brest, BELARUS
- Contact:
Okay, I finally got AC.
You need to print blank line only between cases. And no blank lines after the last case.
You need to print blank line only between cases. And no blank lines after the last case.
Now I lay me down to sleep...
my profile
my profile