## 105 - The Skyline Problem

Moderator: Board moderators

wdg
New poster
Posts: 4
Joined: Tue Aug 16, 2005 3:19 pm
I tested it very carfully, but I could not find the wrong place.

Code: Select all

``````program p105;
var
cache:array[1..100,1..2] of integer;
l,h,r,n,size,k,t:integer;
procedure print_n_clear(j:integer);
{ ouput except the nth elements and so on remain; so does clear operation }
var i:integer;
begin
for i:=1 to j do write(cache[i][1],' ',cache[i][2],' ');
for i:=j+1 to size do begin
cache[i-j][1]:=cache[i][1]; cache[i-j][2]:=cache[i][2];
end;
size:=size-j;
end;
procedure insert(a,b,loct:integer);
var i:integer;
begin
for i:=size downto loct do begin
cache[i+1][1]:=cache[i][1]; cache[i+1][2]:=cache[i][2]; end;
cache[loct][1]:=a; cache[loct][2]:=b; inc(size);
end;
begin
fillchar(cache,sizeof(cache),0);
cache[2][1]:=r; cache[2][2]:=0; size:=2;
while not eof do begin
n:=1; while (n<=size) and (l>cache[n][1]) do inc(n);
if n=size+1 then begin
print_n_clear(size); cache[1][1]:=l; cache[1][2]:=h;
cache[2][1]:=r; cache[2][2]:=0; size:=2;
end
else begin
if cache[n-1][2]<h then begin
if cache[n][1]>r then begin
insert(r,cache[n-1][2],n); insert(l,h,n);
end
else if cache[n][1]<r then begin
insert(l,h,n); inc(n);
while (n<=size) and (r>cache[n][1]) do begin
h:=cache[n][2];
for k:=n to size-1 do begin
cache[k][1]:=cache[k+1][1]; cache[k][2]:=cache[k+1][2]; end;
dec(size); end;
if n=size+1 then begin cache[n][1]:=r;
cache[n][2]:=0; inc(size); end
else insert(r,h,n);
end
end
else if cache[n-1][2]>h then begin
if cache[n][1]<r then
if cache[n][2]<h then begin
t:=cache[n][2]; cache[n][2]:=h; h:=t; inc(n);
while (n<=size) and (r>cache[n][1]) do begin
h:=cache[n][2];
for k:=n to size-1 do begin
cache[k][1]:=cache[k+1][1]; cache[k][2]:=cache[k+1][2]; end;
dec(size); end;
if (n=size+1) then insert(r,0,n)
else insert(r,h,n);
end
else begin
t:=cache[n][2]; n:=n+1;
while (n<=size) and (r>cache[n][1]) do begin
if cache[n][2]<h then begin
t:=cache[n][2]; cache[n][2]:=h; end;
inc(n);
end;
if n=size+1 then insert(r,0,n)
else insert(r,t,n);
end;
end;
end;
end;
print_n_clear(size);
end.``````

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
-sure you need to read all data before you print your answer; you can only calculate the skyline after you know all the buildings.
- I'm not sure how it works in XP (I use Linux), but I think <CTRL>-Z followed by <ENTER> should pass an eof to the program. Personally I prefer to write an input file and pipe it to the program. But with Pascal be carefull with extra blank lines within and at the end of the input.

I have not looked deep into your program, but I think you should rethink and restart from scratch. It is way too complicated (my program is only 17 lines of Pascal). There are only 9999 possible values for the coordinate, so the height of the skyline can be easily stored in an array and adjusted for all buildings.

Endless
New poster
Posts: 1
Joined: Thu Sep 08, 2005 3:29 pm

### 105 WA? Why?

Hi.

Which is the right output to this input:

Code: Select all

``````1 11 5
2 6 7
3 13 9
12 7 16
14 3 25
19 18 22
23 13 29
24 4 28
28 10 39
39 20 39
39 20 39
40 10 50
100 2 101
101 2 300
300 2 500
500 1 520
510 1 540
541 5 542
542 4 542
550 4 560
``````
My output:

Code: Select all

``````1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 10 39 20 39 0 40 10 50 0 100 2 500 1 540 0 541 5 542 0 550 4 560 0
``````

roni
New poster
Posts: 11
Joined: Tue Aug 09, 2005 11:57 am
Contact:
Out of AC code:

1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 10 39 20 39 0 40 10 50 0 100 2 500 1 540 0 541 5 542 0 550 4 560 0
roni(SUST)

moja
New poster
Posts: 1
Joined: Wed Sep 28, 2005 3:41 pm

### 105 - The Skyline Problem

Hello, I don't know in what condition my code will get WA
Could everyone give me some test cases?
Thank you very much!!

The following are test data which I passed.

Code: Select all

``````input:
0 11 5

output:
0 11 5 0
``````

Code: Select all

``````input:
3 2 4
3 1 7
5 2 6

output:
3 2 4 1 5 2 6 1 7 0
``````

Code: Select all

``````input:
1 11 5
2 6 7
3 13 9
12 7 16
14 3 25
19 18 22
23 13 29
24 4 28
28 10 39
39 20 39
39 20 39
40 10 50
100 2 101
101 2 300
300 2 500
500 1 520
510 1 540
541 5 542
542 4 542
550 4 560

output:
1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 20 39 20 39 0 40 10 50 0 100 2 500 1 540 0 541 5 542 0 550 4 560 0
``````

Code: Select all

``````input:
-5 5 1
1 6 2
1 2 7
3 12 10
4 3 5
7 5 20
8 15 12
11 12 13
16 14 19
21 2 22
23 1 30
26 10 28
26 12 27
32 5 36
34 3 38
34 3 40
37 2 42
38 2 44
45 1 46

output:
-5 5 1 6 2 2 3 12 8 15 12 12 13 5 16 14 19 5 20 0 21 2 22 0 23 1 26 12 27 10 28 1 30 0 32 5 36 3 40 2 44 0 45 1 46 0
``````
The following is my code.

Code: Select all

``````//* Q105 The Skyline Problem */
#include <stdio.h>

typedef struct _NODE_T
{
int                h; /* height */
int                r; /* right */
struct _NODE_T*    next;
}NODE_T;

NODE_T*    pt_tail      = {0};
NODE_T*    pt_free_node = {0};
int        left         = -1;

NODE_T* mymalloc(void)
{
NODE_T*    pt_node;

if(pt_free_node != NULL) {
pt_node      = pt_free_node;
pt_free_node = pt_free_node->next;
}
else {
pt_node = (NODE_T*)malloc(sizeof(NODE_T));
}

return pt_node;
}

void myfree(NODE_T* pt_node)
{
if(pt_free_node) {
pt_node->next = pt_free_node;
pt_free_node  = pt_node;
}
else {
pt_free_node  = pt_node;
pt_node->next = NULL;
}
}

/* reduce duplicate item */
void reduce_result(void)
{
NODE_T*    pt_node;
NODE_T*    pt_node2;

for(pt_node = pt_head; pt_node != NULL; pt_node = pt_node->next) {
if(pt_node->next) {
if(pt_node->r == pt_node->next->r) {
if(pt_node->h < pt_node->next->h) {
pt_node->h = pt_node->next->h;
}
pt_node->next = pt_node->next->next;
}
}
}
}

void calculate(int l, int h, int r)
{
NODE_T*    pt_node;
NODE_T*    pt_node2;
NODE_T*    pt_node3;

pt_node       = mymalloc();
pt_node->h    = h;
pt_node->r    = r;
pt_node->next = NULL;

pt_tail       = pt_node;
return;
}

/* check if left bigger than rightest node */
if(l > pt_tail->r) {
pt_node        = mymalloc();
pt_node->h     = 0;
pt_node->r     = l;

pt_node2       = mymalloc();
pt_node2->h    = h;
pt_node2->r    = r;

pt_node->next  = pt_node2;
pt_node2->next = NULL;

pt_tail->next  = pt_node;
pt_tail        = pt_node2;

return;
}

for(pt_node = pt_head; pt_node != NULL; pt_node = pt_node->next) {
if(l <= pt_node->r) {
if(h == pt_node->h) {
if(r <= pt_node->r) { /* new input is under pt_node */
return;
}
else {
l = pt_node->r;
continue;
}
}
else if(h < pt_node->h) {
if(r <= pt_node->r) {
return;
}
else {
l = pt_node->r;
continue;
}
}
else {
if(r == pt_node->r) {
pt_node2       = mymalloc();
pt_node2->h    = h;
pt_node2->r    = r;

pt_node2->next = pt_node->next;

pt_node->r     = l;
pt_node->next  = pt_node2;

if(pt_node == pt_tail) {
pt_tail = pt_node2;
}
return;
}
else if(r < pt_node->r) {
pt_node2    = mymalloc();
pt_node2->h = h;
pt_node2->r = r;

pt_node3    = mymalloc();
pt_node3->h = pt_node->h;
pt_node3->r = pt_node->r;

pt_node->r  = l;

pt_node2->next = pt_node3;
pt_node3->next = pt_node->next;
pt_node->next  = pt_node2;

if(pt_node == pt_tail) {
pt_tail = pt_node3;
}
return;
}
else {
pt_node2      = mymalloc();
pt_node2->h   = h;
pt_node2->r   = r;

pt_node->r    = l;
pt_node3      = pt_node->next;

pt_node->next = pt_node2;

while(pt_node3 != NULL) {
if(pt_node3->r > r) {
break;
}

pt_node2->next = pt_node3->next;
myfree(pt_node3);
pt_node3 = pt_node2->next;
}

if(pt_node3 == NULL) {
pt_tail = pt_node2;
}
else {
pt_node2->next = pt_node3;
}

return;
}
}
}
}

if(h == pt_tail->h) {
pt_tail->r = r;
return;
}

pt_node       = mymalloc();
pt_node->h    = h;
pt_node->r    = r;
pt_node->next = NULL;

pt_tail->next = pt_node;
pt_tail       = pt_node;

return;
}

void print_result(void)
{
NODE_T*    pt_node;

printf("%d", left);
for(pt_node = pt_head; pt_node != NULL; pt_node = pt_node->next) {
printf(" %d %d", pt_node->h, pt_node->r);
}

printf(" 0\n");
}

int main(void)
{
int l, h, r;

while (scanf("%d %d %d", &l, &h, &r)==3)
{
if(left == -1) {
left = l;
}
calculate(l, h, r);
}

reduce_result();
print_result();

return 0;
}
``````

wrcstar
New poster
Posts: 2
Joined: Mon Oct 03, 2005 7:09 pm

### 105 why WA?

This is my code. Why WA?

var skyline : array [0..10000] of integer;
i,l,h,r : integer;
blank : integer;
begin
for i:=0 to 10000 do skyline:=0;
while EoF(input) do begin
for i:= l to r-1 do
if(skyline < h) then skyline:=h;
end;

blank:=0;
for i:=1 to 10000 do
if(skyline[i-1] <> skyline) then begin
if(blank = 0) then begin
Write(i,' ',skyline);
blank:=blank+1;
end
else Write(' ',i,' ',skyline);
end;

end.

BJM
New poster
Posts: 7
Joined: Sat Nov 16, 2002 3:28 pm

1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 10 39 0 40 10 50 0 100 2 500 1 540 0 541 5 542 0 550 4 560 0

Not

1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 20 39 20 39 0 40 10 50 0 100 2 500 1 540 0 541 5 542 0 550 4 560 0

Also, you don't need to worry about negatives since the problem states that all coordinates are positive integers <10,000.

Ming Han
Learning poster
Posts: 77
Joined: Thu Jun 06, 2002 7:10 pm
Location: Singapore
Contact:

Code: Select all

``````#include <stdio.h>

int main(){

int dat[5000][4] = {0};
int c = 0;
int pos[20010] = {0};
int i;

while(scanf("%d %d %d",&dat[c][0],&dat[c][1],&dat[c][2])==3){
for (i=dat[c][0];i<=dat[c][2];i++){
if (dat[c][1]>pos[i]) pos[i] = dat[c][1];
}
c++;
}
int last = 0;

for (i=dat[0][0];i<=dat[c-1][2]+2;i++){
if (pos[i]>last){
printf("%d %d ",i,pos[i]);
last = pos[i];
}else if (pos[i]<last){
if (i==dat[c-1][2]+2) printf("%d %d",(i-1),pos[i]);
else printf("%d %d ",(i-1),pos[i]);
last = pos[i];
}
}
return 0;
}
``````
this is weird! I keep getting PE!
:: HanWorks ::

nukeu666
New poster
Posts: 44
Joined: Sun Feb 13, 2005 1:13 am
Location: India
Contact:
i need help...dunno why im getting WA

Code: Select all

``````#include<stdio.h>
int main()
{
int ht,h[10000],right=0,a,t=0,l[10000],r[10000];
for(a=0;a<10000;a++)
h[a]=0;
while(scanf("%d %d %d",&l[t],&ht,&r[t])==3)
{
if(l[t]>right)
right=l[t];
if(r[t]>right)
right=r[t];
for(a=l[t];a<r[t];a++)
if(h[a]<ht)
h[a]=ht;
t++;
}
ht=0;
for(a=0;a<=right;a++)
{
if(h[a]!=h[a+1]&&ht==1)
printf(" %d %d",a+1,h[a+1]);
if(h[a]!=h[a+1]&&ht==0)
{ht=1;printf("%d %d",a+1,h[a+1]);}
}
}
``````
its working fine for all inputs in this thread

New poster
Posts: 8
Joined: Wed Mar 30, 2005 9:46 am

### 105 Presentation error

What is a presentation error?

#include <iostream>
#include <iterator>
#include <algorithm>

using namespace std;

int main()
{
int space[10000], ans[10000];
ostream_iterator<int> outS(cout," ");

fill(space,space+10000,0);

int i,j,h;
while(cin>>i>>h>>j)
{
for(int p=i;p<j;p++)
{
if(h>space[p]) space[p]=h;
}
}

//output
int last=0;
int end=0;
for(int p=1;p<10000;p++)
{
if(space[p]!=last)
{
ans[end++]=p;
ans[end++]=space[p];
last=space[p];
}
}
copy(ans,ans+end,outS);
cout<<endl;

return 0;
}

Evan Tsang
New poster
Posts: 11
Joined: Sun Jan 02, 2005 9:14 am
Looks like you have a space after the last 0.

f.eliel
New poster
Posts: 10
Joined: Wed Feb 08, 2006 4:31 pm

### 105... Help!

I know these way to read the multiple inputs:

Code: Select all

``````while (scanf("%d %d %d", &li, &hi, &ri)==3) {
``````
But i don't know how to make it stop reading.
I looked at a lot of topics but i couldn't find it.
Can anyone help me?
Thanks.

f.eliel
New poster
Posts: 10
Joined: Wed Feb 08, 2006 4:31 pm
I realized tha i was not doing anything wrong, i just didn't the problem...
But now i having trouble in the output. I don't know how to get the space after the last zero of...

ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China
I don't understand what you mean. But I know there is no space after the last zero.
I stay home. Don't call me out.

f.eliel
New poster
Posts: 10
Joined: Wed Feb 08, 2006 4:31 pm

### 105 WA

I don't understand why i got WA...
Last edited by f.eliel on Tue Feb 28, 2006 9:34 pm, edited 1 time in total.