dreaded skyline D&C algo

This is a discussion on dreaded skyline D&C algo within the C++ Programming forums, part of the General Programming Boards category; hey all...I'm working on this Skyline problem, and I'm stuck. I'm not really sure how to merge the two arrays ...

  1. #1
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Posts
    2,572

    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?

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

  2. #2
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Posts
    2,572
    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);
    
    
    }
    Last edited by axon; 11-06-2003 at 07:51 PM.

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

  3. #3
    carry on JaWiB's Avatar
    Join Date
    Feb 2003
    Location
    Seattle, WA
    Posts
    1,972
    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)
    {
    //...
    }
    "Think not but that I know these things; or think
    I know them not: not therefore am I short
    Of knowing what I ought."
    -John Milton, Paradise Regained (1671)

    "Work hard and it might happen."
    -XSquared

  4. #4
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Posts
    2,572
    thanks jawib...I emailed my prof and he let me do it with linked lists 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?

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. flow control algo
    By Mr.Bit in forum C Programming
    Replies: 4
    Last Post: 04-28-2008, 10:32 AM
  2. Maze generation algo
    By VirtualAce in forum Game Programming
    Replies: 7
    Last Post: 03-01-2006, 04:03 AM
  3. Figuring Algo for assignment
    By axon in forum C++ Programming
    Replies: 4
    Last Post: 10-30-2003, 10:03 AM
  4. base conversion algo
    By Unregistered in forum C++ Programming
    Replies: 2
    Last Post: 12-28-2001, 08:28 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21