# dreaded skyline D&C algo

Printable View

• 11-06-2003
axon
dreaded skyline D&C algo
hey all...I'm working on this Skyline problem, and I'm stuck. I'm not really sure how to merge the two arrays together according to the requirements. If you are not familiar with the Skyline Problem here it is in a nutshell:

There is a city with no hills and has a set of rectangular buildings. Suppose you are viewing the city from water. Leftmost position of city is used as reference point ( horiz position 0 ). This, a building can be speified by (l, h, w), where l gives the left boundary, h the height of the buildingsm and w its width.

the program will take as input a set of n buildings, in no particular order. The program now has to extract the outline formed by the buildings. This skyline will be formed by a sequence of horizontal segments starting at position 0. It will be represented by a equence of pairs (h, w) where h is the height abd w the width.
Code:

```So basically if the input from a file is: (13, 3 4), (3,6,6,), (1,2,9), (14, 2,5), (18,4,2) the corresponding output will be: (0,1), (2,2), (6,6), (2,1),(0,3),(3,4),(2,1),(4,2)```
Unfortunately one of the requirements is that I have to use arrays, which is very annoying. It would be much simpler using linked lists.... anyways, here is the code I have so far...and the following errors arise about my recursion:
Code:

`main.cpp(81) : error C2668: 'divide' : ambiguous call to overloaded function`
Code:

```#include <iostream> #include <cstdlib> #include <cctype> #include <string> #include <fstream> using namespace std; struct Skyline {         int x;         int y;         Skyline *n; }; int* divide( int *B, int *O, int n); void skyMerge(int *, int, int*, int, int*, int); int main() {                 ifstream inFile;                //text file IO                 ofstream outFile;                                 string inFileName;                                string outFileName;                                 int numberOfBuildings;        //first number from file                 //float descriptions;                 char tmp[1];                        //holding the characters from file                 int i = 0;                                //counter                 int j = 0;                                //counter                                 inFile.open("hey.txt");         inFile>>numberOfBuildings;                 //allocating memory for the size of the input file                 int *B = new int[numberOfBuildings*3];                 int *O = new int[numberOfBuildings*3];                                 for( i = 0; i < (numberOfBuildings*7); i++ ){                         inFile>>tmp[0];                         if( isdigit(tmp[0]) ) {                                 B[j] = atoi(tmp);                                 j++;                         }                 }                                divide(B, O, numberOfBuildings);         return 0; } int* divide(int *B, int *&O, int n) {         if ( n == 1 )         {                 return O;         }                 int n1 = (n/2);         int n2 = (n - n1);         int *skyLeft = new int[n1*3];         int *skyRight = new int[n2*3];         divide(B, skyLeft, n1);         divide(B, skyRight, n2);         skyMerge(skyLeft, n1, skyRight, n2, O, n); } void skyMerge(int *s1, int n1, int *s2, int n2, int *&O, int n) { }```
any ideas? suggestions?
• 11-06-2003
axon
I fixed that one error....but I still think that I'm not doing it right.
Code:

```int* divide(int *B, int *&O, int n, int maxWidth) {         if ( n == 1 )         {                 return O = B;         }                 int n1 = (n/2);         int n2 = (n - n1);         int *skyLeft = new int[n1*3];         int *skyRight = new int[n2*3];         divide(&B[n1], skyLeft, n1, maxWidth);         divide(&B[n2], skyRight, n2, maxWidth);         //skyMerge(skyLeft, n1, skyRight, n2, O, n); }```
• 11-06-2003
JaWiB
Code:

`int* divide(int *B, int *&O, int n, int maxWidth)`
What are you trying to pass to the function? Arrays? Or do you want a single integer to be passed? If you need to be able to change the variable, but it is not an array, try a reference :

Code:

```int* divide(int& B, int& O, int n, int maxWidth) { }```
Also note that I don't know what you want to do with the return value, so you may want to change that as well.

If you are trying to pass an entire array, pass pointers (remove the '&' before the 'O'):
Code:

```int* divide(int* B, int* O, int n, int maxWidth) { //... }```
• 11-06-2003
axon
thanks jawib...I emailed my prof and he let me do it with linked lists:D :D :D hurrah! I'll post the finished prog later tonite.

I do hate arrays in complicated algos....seriously this is a data struct class....so why did he make the array requirement?