CS 503 - Advanced Programming I Programming Assignment 1

Programming Assignment 1 - Swimming Pool Placement

Advanced Programming I, Spring 2006

Due Date

This assignment is due by 5:30 p.m. on Tuesday, 31 January.

See the assignment turn-in page (last modified on 18 January 2006) for instructions on turning in your assignment.

I build swimming pools. My clients want the biggest rectangular pool possible measured in square feet. The yards in which the pools should be built have trees, decks and other obstructions in them, and my customers don't want any of the obstructions to be removed or changed. For safety and easy maintenance, there is a continuous, one-unit gap around each obstruction in which a pool should not be built. However, a pool edge may but up against and edge of the yard (with no obstructions the pool will fill the yard).

The Problem

Write a program that reads from std-in a description of a yard and writes to std-out a description of the largest pool that will fit in the yard.

For simplicity, both the yard and the obstructions will be rectangles. Obstacles may overlap, but will not extend past the boundaries of the yard.

Input

Input is a sequence of lines with the following format:

yard-height yard-width
min-x₁ min-y₁ height₁ width₁
...
min-x_n min-y_n height_n width_n

where min-x_i, min-y_i, height_i, width_i, yard-height, and yard-width are non-negative integers separated by one or more space characters.

The first line of input describes the yard's area; each remaining input lines describes an obstacle that has its lower-left corner at (min-x_i, min-y_i) in the yard (the lower left-hand corner of the yard is (0, 0)) and has area height_i×width_i.

Any input not of this form is incorrect, as is any input that describes invalid obstacles. If you program reads incorrect input, it should print an informative error message to std-err and exit.

For example, the input

5 6
0 3 2 2
4 0 3 2

describes a 5×6 yard with two obstacles:

an example yard

Output

Normal output is written to std-out as a single line of text with the format

min-x min-y height width

where min-x, min-y, height, and width are non-negative integers separated by one or more space characters. The single line of output describes a pool with its lower-left corner at (min-x, min-y) in the yard and with area height×width. If there is more than one maximal pool possible, your program may output any one of them. For example, the output

0 0 2 3

describes the solution

an maximal pool

to the problem given in the input section.

If your program encounters an error, it should print on std-err a single line of text describing the error and then exit with no further processing. The error message should start with an exclamation point (!). For example, the input

5 6
2 3 10 10

should cause your program to write something like the following

! Obstacle not contained within the yard.

to std-err and exit with no further processing or output.

Testing

The script gen-yard, when run, writes to std-out a yard description suitable for input to your program. Although you can pipe the output of gen-yard directly into your program

$ gen-yard | mpool

it's probably easier for testing if you capture gen-yard output in a file, which you can then repeatedly input to your program:

$ gen-yard > yard

$ mpool < yard

gen-yard can be found in the public class directory /export/home/class/CS-503/a1. My solution to the problem (compiled for Linux) can also be found in the same directory.

This page last modified on 7 February 2006.