## 105 - The Skyline Problem

Moderator: Board moderators

yan8381
New poster
Posts: 4
Joined: Wed Nov 26, 2003 4:05 pm
you vector length is 500, I think that is too small, because "All coordinates of buildings are positive integers less than 10,000 ". so I denfine the vector is 100002,that is better.

and another problem is your output.
for example, your output is: 2^3^4^('^'means space)
but,the output should be:2^3^4'/n'

RyanCHEN
New poster
Posts: 2
Joined: Thu Dec 04, 2003 6:05 pm

### OK!

I got the error since I used the member fuction of vector .at()
the system didnt like that:)

thank you Yan anyway!:)

maxpayne
New poster
Posts: 2
Joined: Thu Jan 01, 2004 5:33 pm
Location: Jakarta
Contact:

### why runtime error????? 105 (skyline problem)

I don't understand why I got runtime error for my program. Here it is:
[cpp]
#include <iostream>
#include <string>
using namespace std;

class skylines {
unsigned int left[5000];
unsigned int height[5000];
unsigned int right[5000];
unsigned int most;
static unsigned int i;
public:
skylines() : most(0) {
memset(left,0,sizeof(left));
memset(height,0,sizeof(height));
memset(right,0,sizeof(right));
}
void input(const unsigned int l, const unsigned int h, const unsigned int r);
};

unsigned int skylines::i = 0;

unsigned int j=0;
short int flag=0,same=0;
unsigned int temp=0,left_temp=0,right_temp=0;

for(unsigned int i=left[0]; i<=most; i++) {
j=0;
if(temp==0) {
while((left[j]<=i)&&(left[j]!=0)) {
if(right[j]<i) {
j++;
continue;
}
else {
if(temp<height[j]) {
temp = height[j];
left_temp = left[j];
right_temp = right[j];
flag=1;
}
j++;
}
}
if(flag==1) {
cout << i << " " << temp << " " ;
flag=0;
if(left_temp==right_temp) i--;
}
}
else {
if(i==right_temp) {
temp = left_temp = right_temp = 0;
while((left[j]<=i)&&(left[j]!=0)) {
if(right[j]<=i) {
j++;
continue;
}
else {
if(temp<height[j]) {
temp = height[j];
left_temp = left[j];
right_temp = right[j];
}
j++;
}

}
cout << i << " " << temp << " " ;
}
else {
while((left[j]<=i)&&(left[j]!=0)) {
if(right[j]<i) {
j++;
continue;
}
else {
if(temp<height[j]) {
temp = height[j];
left_temp = left[j];
right_temp = right[j];
flag=1;
}
j++;
}

}
if(flag==1) {
cout << i << " " << temp << " " ;
flag=0;
if(left_temp==right_temp) i--;
}
}
}//end of else if
}//end of for

}

void skylines::input(const unsigned int l, const unsigned int h, const unsigned int r ) {
left = l;
height = h;
right = r;
if(most<right) most = right;
i++;
}

int main() {
skylines user;

unsigned int l,h,r;

while(cin >> l >> h >> r) {
user.input(l,h,r);
}

int x;
cin >> x;

}
[/cpp]
Be a good world citizen by keeping this planet clean!!!!

scruff
New poster
Posts: 29
Joined: Wed Dec 24, 2003 5:22 am
Well, it died with an "invalid memory reference" so check your indexes on your arrays and verify they don't go outside their bounds

maxpayne
New poster
Posts: 2
Joined: Thu Jan 01, 2004 5:33 pm
Location: Jakarta
Contact:
Thank you. I solved my problem now although why I got Presentation Error is still mistery for me.
Be a good world citizen by keeping this planet clean!!!!

scruff
New poster
Posts: 29
Joined: Wed Dec 24, 2003 5:22 am
Well, i have a couple of comments. I have not run your code yet but it seems that it always outputs a blank space after every cout which is fine until the last entry and then you should not print the space. This will give a presentation error. The second is what is that last cin in your main() for?

Gazi Shaheen Hossain
New poster
Posts: 7
Joined: Fri Sep 03, 2004 6:47 pm

### 105 WA

Why this gives WA?
help me.
[cpp]
#include "stdio.h"

void main()
{

int arr[10000]={0},i,L,H,R,Rm=0;
while(scanf("%d %d %d",&L,&H,&R)==3)
{
if(Rm<R)Rm=R;
for(i=2*L;i<=2*R;i++)
if(arr<H)
arr=H;
}
i=0;
if(arr[0]!=0)printf("0 %d ",arr[0]);
char flag=0;
for(i=1;i<=2*(Rm+1);i++)
{

if(arr>arr[i-1])
{if(flag)printf(" "); flag=1;
printf("%d %d",i/2,arr);}
else if(arr<arr[i-1])
{if(flag)printf(" "); flag=1;
printf("%d %d",(i-1)/2,arr);}

}
}
[/cpp]

afonsocsc
New poster
Posts: 34
Joined: Mon Mar 24, 2003 1:15 am
Location: Portugal, Lisbon
Hello,
You have an array of 10000, but you use 2*L and 2*R, since the numbers for L and R will be as high as 9999, your program will be accessing memory outside of the array.

for example, with this input:
4090 5000 5000

4090 5000 5000 1073833120 5000 -1073744880 5001 -1073744764

Hope it helps

efr_shovo
New poster
Posts: 38
Joined: Wed Sep 22, 2004 9:09 am

### 105 Why P.E.

i got p.e. why? Pleaze help me
#include<stdio.h>

int a[20000];
int l,r,h,i,j,max=0,mutex=0;

void main()
{
while(3==scanf("%d %d %d",&l,&h,&r))
{
for(i=l;i<=r;i++)
if(a<h)
a=h;
}

for(j=0;j<=i;j++)
{
if(a[j]>a[j+1])
{
max=j;
mutex=1;
}
else if(a[j]<a[j+1])
{
max=j+1;
mutex=1;
}
if(mutex==1)
{
printf("%d %d ",max,a[j+1]);
mutex=0;
}
}
printf("\n");
}

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
you print unnecessary space at end of the line. Try to avoid this character, and I think you got Acc without PE.

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

straggler73
New poster
Posts: 1
Joined: Wed Dec 01, 2004 8:22 pm

### 105 - The Skyline Problem

#include <stdio.h>

#define MAX 10000

int height[MAX+1];

int main()
{
int i;
int li, hi, ri;

for(i=0; i<= MAX; i++)
{
height = 0;
}

while (scanf("%d %d %d\n",&li, &hi, &ri)==3){
for(i=li; i < ri; i++)
{
if (height < hi)
height = hi;
}
}

for(i=1; i<= MAX; i++)
{
if (height[i-1] != height)
{
printf("%d %d ", i, height);
}
}
return 0;
}

Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET
The problem statement says that -
The coordinates must be separated by a blank space.
But I think u r printing an space after the last co-ordinate, too. Hope it helps.
You should never take more than you give in the circle of life.

lazenca
New poster
Posts: 18
Joined: Sat Sep 18, 2004 2:14 pm
Location: Dongguk University@COREA
Contact:

### #105 WA help me...

I tested some data with this code...but I got WA...
plz help me..

Code: Select all

``````#include <stdio.h>
#include <stdlib.h>      /*   malloc   */

typedef struct buildingTriple *pBuildingTriple;
typedef struct buildingTriple {
unsigned int   left;           /*   left coordinate of building   */
unsigned int   right;          /*   right coordinate of building   */
unsigned int   height;         /*   height of building   */
pBuildingTriple next;          /*   link to next node   */
pBuildingTriple back;          /*   link to back node   */
} buildingTriple;

void   insert_to_list(pBuildingTriple ptr, pBuildingTriple node);

int main()
{
buildingTriple   head;        /*   list for buildings   */
buildingTriple   in_node;       /*   inputed coordinates of building   */

/*   temp variable   */
unsigned int   temp;
unsigned int   pre_right_coord;

while (scanf("%u %u %u", &in_node.left, &in_node.height, &in_node.right) == 3)
.
.
.
.
.

``````
Last edited by lazenca on Fri Apr 08, 2005 3:15 am, edited 2 times in total.
I see the red...
I saw the rain..

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore
The error in your code is obvious - check the way you output. You are printing everything on one line, that is the main reason for your code getting WA.

[c]

/************************************************************************/
/* OUTPUT PART */
/************************************************************************/
{
if (w_ptr == head.next || w_ptr->left >= pre_right_coord)
{
printf("%u %u ", w_ptr->left, w_ptr->height);
pre_right_coord = w_ptr->right;
}
else
{
printf("%u 0 ", pre_right_coord);
}
}
printf("%u 0\n", pre_right_coord);
[/c]

Add in a \n - newline character for the last printf as shown above and your code should work fine.

lazenca
New poster
Posts: 18
Joined: Sat Sep 18, 2004 2:14 pm
Location: Dongguk University@COREA
Contact: