105 - The Skyline Problem

[10153EN]

That's why you got PE~

Try to put a newline character at the end and you will get Accepted.

[Pokemonster]

Thanks alot guys! Works fine now

[nariini]

i don't know why received wrong answer..

sample inputs generate correct outputs.

let me know please

[java]
import java.io.*;
import java.util.*;

class Main
{
static String ReadLn (int maxLg)
{
byte lin[] = new byte [maxLg];
int lg = 0, car = -1;
String line = "";

try
{
while (lg < maxLg)
{
car = System.in.read();
if ((car < 0) || (car == '\n')) break;
lin [lg++] += car;
}
}
catch (IOException e)
{
return (null);
}

if ((car < 0) && (lg == 0)) return (null); // eof
return (new String (lin, 0, lg));
}

public static void main(String[] args)
{
Main myWork = new Main();
myWork.Begin();
}

void Begin()
{
String line;
StringTokenizer idata;
int arr[];
int top_pnt[];
int i=0;
int end_pnt = -1;
int cnt=0;

arr = new int[15000];
try
{
while ((line = Main.ReadLn(255)) != null) //input&#44050;&#46308;&#51012; array&#50640; &#51200;&#51109;
{
cnt++;
if (cnt > 5000)
{
System.exit(1);
}
idata = new StringTokenizer(line);
arr = Integer.parseInt(idata.nextToken());
arr[i+1] = Integer.parseInt(idata.nextToken());
arr[i+2] = Integer.parseInt(idata.nextToken());
if (arr<1 || arr>10000 || arr[i+1]<1 || arr[i+1]>10000 || arr[i+2]<1 || arr[i+2]>10000)
{
System.exit(1);
}
i = i + 3;
}
} catch(Exception e){}
for (int j=2; arr[j] != 0; j=j+3) //&#52572;&#45824; &#50864;&#52769;&#44050; &#51200;&#51109;
{
if (end_pnt < arr[j])
end_pnt = arr[j];
}
top_pnt = new int[end_pnt+1]; //creat top_pnt array
for (int j=0; j <= end_pnt; j=j+3) //top_pnt&#47484; top_pnt[]&#50640; &#51200;&#51109;
{
for (int k=arr[j]; k < arr[j+2]; k++)
{
if (top_pnt[k] < arr[j+1])
top_pnt[k] = arr[j+1];
}
}
int temp = 0;
int flag = 0;
for(int j=arr[0]; j<=end_pnt; j++)
{
if (temp != top_pnt[j])
{
temp = top_pnt[j];
if (flag == 0)
{
System.out.print(j+" "+top_pnt[j]);
flag = 1;
} else if (flag == 1){
System.out.print(" "+j+" "+top_pnt[j]);
}
}
}
}
}
[/java]

[soyoja]

Hhm... In fact, I don't know about java. ( I solved this problem in C++ )

So I can't say about your code. ( Perhaps your code has some mistakes. )

But I think that it's one of the easiest problem in valladolid problem set.

How about use this sample test data? Maybe it gives you the opportunity

to solve this problem.

P.S ) Are you Korean? If you are Korean, I strongly recommend

that reading 2001 ACM Taejon problem F, Moving tables. It use very

simuliar solution to this problem. Good luck.

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

[dawynn]

I agree, this is a very easy problem. The description has changed some since I solved this, though. At the time, the trick was that some of the coordinates could be less than 0, but always with an absolute value less than 10000. Even though they now promise positive integers, I would allow for 0 as a possible coordinate value.

Try the sample input again, but change the first line to: 0 11 5. The output then should of course also start with 0.

[zalileo]

Thanks a lot for soyoja's sample data!


finally, I get it with 0.020 CPU time

[chimera]

I solved these cases listed above.
But I still got wrong answer.
Who could give me some tips, thanks?

[cherlee]

i don't understand java and i'm having a trouble in solving this problem although it's said to be one of the easiest.. ^^

could someone help me to explain the logic?? i'll try to convert it into c coding by myself.. thx..

[dawynn]

This is probably not the best algorithm -- but it should work.

Create a 20001 integerarray. Set all values to 0 initially.

As you read in each triplet, add 10000 to the starting and ending coordinates in the triple. This takes care of any cases where buildings are specified with negative start or end values. A negative height doesn't happen since it wouldn't make sense anyway. You wouldn't notice a hole in the ground as you look at a skyline.

For each of the locations from the altered beginning coordinate to the altered ending point (include the starting point, exclude the ending point), check the current height. If the new height is more than the current height -- save the new height in the array. This takes care of overlapping buildings. Only the tallest building becomes part of the skyline.

Once all triples have been read in, scan the array. Starting from the beginning of the array, scan until you find some height other than 0. At that point, subtract 10000 from the array index and print that location number, then give its current height, then scan until the height changes again. Then keep alternating printing new coordinates and new heights. Just remember to subtract 10000 from the array index each time for the coordinate.

David

[Olorin]

So, p 105 is an example, but not the only one.
In many problems we have to read input until the end of the stream. Now, if this was a file (for ex named infile), we could have loops that check on infile.fail, or loops while(infile) (depending).
Since this is cin, not a filestream, how do you keep on reading till there is input?

For instance, p105 has the input made up of triplets of integers.
So, I have the following (ok, with cuts and removals :
[cpp]
#include <cstdlib>
#include <cmath>
#include <climits>
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

void main()
{
int n;
vector<Bld> buildings;
int maxR=-1;

while(cin>>n)
{
// read two more integers with
// cin>>myInt;
// and do stuff with them
}//WEND
// Do more stuff

}
// End main
[/cpp]

Of course, when I try to test it,
I enter the numbers I wish, press Enter, enter 3 more numbers, and so on. However, the program cannot understand when I am done with my entering data and move out of that while loop to Do More Stuff.

Ehr... how do you people do it?

Thanks in advance.

[Olorin]

Well, I did post this in the Volume I forum, but maybe it is more appropriate here in C++. ANyhow, the question makes explicit reference to P105, but disregard that, since it is really a generic problem I'm having because the inputs here come from cin rather than a filestream.

=================================

So, p 105 is an example, but not the only one.
In many problems we have to read input until the end of the stream. Now, if this was a file (for ex named infile), we could have loops that check on infile.fail, or loops while(infile) (depending).
Since this is cin, not a filestream, how do you keep on reading till there is input?

For instance, p105 has the input made up of triplets of integers.
So, I have the following (ok, with cuts and removals :

[cpp]

#include <cstdlib>
#include <cmath>
#include <climits>
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

void main()
{
int n;
vector<Bld> buildings;
int maxR=-1;

while(cin>>n)
{
// read two more integers with
// cin>>myInt;
// and do stuff with them
}//WEND
// Do more stuff

}
// End main

[/cpp]

Of course, when I try to test it,
I enter the numbers I wish, press Enter, enter 3 more numbers, and so on. However, the program cannot understand when I am done with my entering data and move out of that while loop to Do More Stuff.

Ehr... how do you people do it?

Thanks in advance.

[Fresh]

Try this - Store the sample input in a file, let's say input.txt. Make executable file (p105.exe) and at command prompt, test the output by typing 'c:\p105 < input.txt'. You can print the output to a file with 'c:\p105 < input.txt >output.txt'

-novice

[zorbathut]

For submission, the code you've got there will work beautifully - it'll hit end-of-stream and go into More Stuff.

For testing purposes, I recommend coming up with a sentinel value to indicate "end of stream" - if( n == -2 ) break; - and then write -2 to end it. Just remember to pull it out before submitting, if -2 is valid input ;)

[EZE]

Yeah... the while(cin >> blah) works well for the submissions. However, when reading from standard input that isnt re-directed, you have to tell cin that it's at the end of the stream. This is done by hitting ctrl-d (^d) then enter. I'm not sure if this works under dos (or windows)... but who uses them anyways? Hope that helps!

ciao
EZE

[Olorin]

Thanks EZE, and Zorba. I'll try to submit it as-is and come up with a testing scheme using files or sentinel values.