Simple procedural program that finds a smallest rectangle to accommodate a given set of rectangles

gistfile1.cpp

#include <iostream>
#include <cmath>
using namespace std;

struct placedRect
{
	int x,
		y,
		width,
		height;
};

struct rectToPack
{
	int width,
		height,
		area,
		weight;
};

void swap(int& a, int& b) 
{
	a+=b;
	b=a-b;
	a-=b;
}

bool print_layout(char* a, int width, int height) 
{
	for (int i=0; i<height; i++) {
		for (int j=0; j<width; j++) {
			cerr << a[i+j*height];
		}
		cerr << "\n";
	}
	return true;
}

int compare_weights (const void * a, const void * b)
{
	return (*((int*)b+3) - *((int*)a+3));
}

int find_next_divisor(int number, int previous) 
{
	for (int i=previous+1; i<=sqrt(number); i++)
		if (number % i == 0)
			return i;
	return 0;
}

void place(char * bin, placedRect best, int const height, char * layout)
{	
	int xBoundary=best.x+best.width;
	for (int i=best.x; i<xBoundary; i++) //from left side to right
		memset(bin+i*height+best.y,'\1',best.height); //set all columns to 'x's
	
	int x1=best.x, 
		x2=best.x+best.width-1, 
		y1=best.y, 
		y2=best.y+best.height-1;
	
	//drawing
	layout[x1*height+y1] = '+';
	layout[x1*height+y2] = '+';
	layout[x2*height+y1] = '+';
	layout[x2*height+y2] = '+';
	
	for (int i=x1+1; i<x2; i++) {
		int j=y1;
		layout[i*height+j] = '-';
		j=y2;
		layout[i*height+j] = '-';
	}
	for (int j=y1+1; j<y2; j++) {
		int i=x1;
		layout[i*height+j] = '|';
		i=x2;
		layout[i*height+j] = '|';
	}
}

int scores(char * bin, placedRect pos, int const width, int const height)
{	
	int score=0; 
	int const i=pos.x, j=pos.y, fw=pos.width, fh=pos.height, iw=i+fw, jh=j+fh;
	
	//find left side touching perimeter
	if (i==0) {
		score+=fh;
	} else if (i-1>=0) {
		int n=i-1;
		for (int m=j; m<jh; m++) {
			if (bin[n*height+m]) {
				score++;		
			}
		}
	}
	//find bottom side touching perimeter
	if (j==0) {
		score+=fw;
	} else if (j-1>=0) {
		int m=j-1;
		for (int n=i; n<iw; n++) {
			if (bin[n*height+m]) {
				score++;		
			}
		}
	}
	//find right side touching perimeter
	if (iw==width) {
		score+=fh;
	} else if (iw<width) {
		int n=iw;
		for (int m=j; m<jh; m++) {
			if (bin[n*height+m]) {
				score++;
			}
		}
	}
	//find top side touching perimeter
	if (jh==height) {
		score+=fw;
	} else if (jh<height) {
		int m=jh;
		for (int n=i; n<iw; n++) {
			if (bin[n*height+m]) {
				score++;		
			}
		}
	}
	return score;
}

bool fits(char * bin, placedRect pos, int const height)
{
	int const ip = pos.x+pos.width;
	//checking if all cells are 0's
	for (int i=pos.x; i<ip; i++)
	{
		if (memchr(bin+i*height+pos.y, '\1', pos.height)) 
			return false;
	}
	return true;
}

bool allocate(char* bin, rectToPack file, placedRect &best, int width, int height)
{
	int orientations=2, score=0;
	bool foo = false;
	if (file.width==file.height)
		orientations=1;
	for (int i=0; i<orientations; i++) {
		if (i==1) //rotate file
			swap(file.width, file.height);
		
		int fWidth = file.width, fHeight = file.height, 
			wBoundary = width-fWidth+1, hBoundary = height-fHeight+1;
		
		//find the best position
		for (int j=0; j<wBoundary; j++) {
			for (int k=0; k<hBoundary; k++) {
				if (!bin[j*height+k]) {
					placedRect pos;
					pos.x=j;
					pos.width=fWidth;
					pos.y=k;
					pos.height=fHeight;
					if (fits(bin, pos, height)) {
						int scorebar = scores(bin, pos, width, height);
						if (scorebar>score) {
							score=scorebar;
							best=pos;
							foo=true;
						}
					}
				}
			}
		}
		
		if (i==1) //rotate back
			swap(file.width, file.height);
	}
	return foo;
}

bool packs(rectToPack files[], int n, int area, int div)
{
	int width;
	if (!(width = area/div)) return false;

	char* bin, * layout;
	bin = new (nothrow) char[area];
	layout = new (nothrow) char[area];
	if (bin == 0 || layout == 0) {
		cout << "Error: " << area << " bytes could not be allocated";
		return false;
	}
	memset(bin, '\0', area);	
	memset(layout, ' ', area);

	placedRect best;
	//try to place
	for (int i=0; i<n; i++) {		
		if (allocate(bin, files[i], best, width, div)) {
			place(bin, best, div, layout);
		} else {
			delete[] bin;
			delete[] layout;
			return false;
		}
	}
	print_layout(layout, width, div);
	delete[] layout;
	delete[] bin;
	return true;
}

bool is_enough(rectToPack files[], int n, int area, int maxw, int maxh)
{
	int div = maxh - 1;
	div = find_next_divisor(area, div);
	if (div==0 || area/div<maxw) {
		return false;
	}
	//try to pack
	while (!packs(files, n, area, div)) {
		div = find_next_divisor(area, div);
		if (div == 0) {
			return false;
		}
	}
	return true;
}

int main (int argc, char * const argv[]) {
	int n;
	cin >> n;
	
	if (n>0) {
		rectToPack* files;
		files = new (nothrow) rectToPack[n];
		if (files == 0) {
			cout << "Error: " << n*4 << " bytes could not be allocated";
			return false;
		}
		int maxHeight=0, maxWidth=0, totalArea=0;
		
		//reading input to files, calculating areas and weights, max width and height
		for (int i = 0; i < n; i++) {
			cin >> files[i].width >> files[i].height;
			if (files[i].width < files[i].height)
				swap(files[i].width, files[i].height);
			if (files[i].width > maxWidth)
				maxWidth=files[i].width;
			if (files[i].height > maxHeight)
				maxHeight=files[i].height;
			int perimeter = 2*(files[i].width + files[i].height);
			files[i].area = files[i].width * files[i].height;
			totalArea+=files[i].area;
			files[i].weight = sqrt(files[i].area)*perimeter;
		}
		
		qsort(files, n, sizeof(*files), compare_weights);
		int area = totalArea;
		while (true) 
		{
			if (is_enough(files, n, area, maxWidth, maxHeight)) {
				cout <<area;
				return 0;
			} else if (area > 2*totalArea) {
				cout << "-1\n";
				return 0;
			} else{
				area++;
			}
		}
		delete[] files;
	} else {
		cout << "-1\n";
	}
	return 0;
}