One difficult problem in computer science is to calculate the area of a collection of possibly overlapping rectangles. For small data sets it is possible to take a fairly naive approach to this problem and use a two dimensional array as a method of counting units.
You are to write a program that computes the total area used by a set of overlapping rectangles given in a data file. The data file will consist of 4 values on each line. The 4 values will define the lower left corner and upper right corner of the rectangle to be added.
We have provided two sample input files: Run1.dat and Run2.dat and a sample executable. Click on the link to download the executable and save it on your M drive. Open the DOS window and use the CD command to find the file if necessary and type 'rect' (without the quotes) to see the sample program run.
You must define a structure called Point that a pair x and y
of integer values.
(The integer x will be between 0 and 78; the integer y will be between 0 and 22.)
You must define a structure called Rect that
hint: a rectangle can be described by two points.
You must also define a structure called Screen which consists of a two dimensional array and its size.
The following functions should be implemented:
void init_screen(Screen& s); /* This function initializes the 'screen' setting its dimensions and filling the area with periods (nothing is printed to the computer monitor here!). */ void draw_screen(Screen s); /* This function copies the contents of the screen s onto the computer monitor. */ void make_rectangle(int x1, int y1, int x2, int y2, Rect& r) /* This function constructs the rectangle r so that the lower left corner is (x1, y1) and the upper right corner is (x2, y2). */ void insert_rectangle(Screen& s, Rect r) /* This function places the rectangle r onto the 'screen' by placing *'s in the locations representing the rectangle. */ int compute_area(Screen s) /* This function computes the area used by rectangles currently on the screen. It returns the total number of *'s. */
We have provided a driver program that you may use for your assignment. It is highly suggested that you write the functions one at a time testing each function with your own driver program, then substituting our driver program at the end.