Write a C program that, given an input file that contains: a grid size (representing blocks in a neighborhood), coordinates of bakery-cafe locations, and customer survey responses; generates as output, a file with the maximum number of locations that can be accessed for each given survey response and the optimal coordinate from which a person can access them.

The Sunrise bakery-cafe chain has several locations in different parts of the far, far away city. City folks love coffee and donuts from Sunrise ❤☕���, so the local “kitties in booties” real estate company is interested in identifying landmarks that represent a good deal to build rental apartments that is based on proximity to Sunrise locations in the neighborhood.

 

To perform the valuation analysis, a map of the neighborhood marked with Sunrise locations is used. Assuming the average person is willing to walk a certain number of blocks to get their morning coffee, you need to find the coordinates from which a person can access the maximum number of Sunrise locations. A map has a grid layout (matrix), with blocks aligned on the northsouth and east-west axes. Since we need to walk through the streets to reach a location, the distance between the intersections (a,b) and (c,d) is given by the equation: |a − c| + |b − d|.

 

Instructions:

 

The source file for this assignment will be named p2_<username>_<labsection>.c

When you run your program, you will enter the input filename on the command line as follows:

 

p2_<username>_<labsection> <input_file> 

 

Input:

 

Each input file could contain several test cases. The first line of each test case contains four integers dx, dy, n, r. These values represent: the dimensions of the grid dx×dy, (1<dx≤100) and (1<dy≤100), the number of locations n (0≤ n≤8000) and the number of responses for a survey r (1<r≤20). Each of the next n lines contains two integers xi and yi, (1≤ xi ≤ dx, 1 ≤ yi ≤ dy) these specify the coordinates of the i^th Sunrise location. Each of the next r lines contains an integer max(0≤max≤100), which is the maximal distance that a person is willing to walk for a cup of coffee to a Sunrise location. The end of the test cases is a line containing four zeros.

 

Assumptions:

• There is at most one Sunrise location per intersection (coordinate)
• The nvalue for a test case is at most the grid size (n≤dx×dy)
• Range and type for dx, dy, n, rare correct
• Line 0 0 0 0to indicate the end of test cases is always present
• The input filename contains a single dot (.) an its extension (txt, in, etc.)

 

Output:

 

The program will print the results in an output file whose name will be the same as the input file but with the extension .out. If run is successful, the program prints the message “Output file: <output_file.out> created successfully”. Within the file, each instance is labeled as Instance #:, where # is the corresponding test case (the first case is 1, the second 2, and so on). Then, display a line for each survey response (r). Each line displays the maximum number of bakery-cafe locations that could be accessed for the maximal distance (max) that a person is willing to walk in that survey response followed by the optimal coordinate in the grid (x,y). Then, display the solution as a manner of a “map”, where each line grid is printed on a new line using ‘-‘ for an empty cell grid, ‘*’ for a Sunrise location, and ‘$’ to represent the optimal coordinate. Use ‘@’ when an optimal coordinate is the same as a Sunrise location.

Note:

• A location is in a square, thus a person can walk “over” it to access any grid intersection.
• If for a given test case, the same coordinate appears more than once, i.e., it is the same coordinate for more than one survey response, just use a single ‘$’ in the cell grid.
• If there is a tie, choose the min-ycoordinate as the first criterion and the min-x coordinate as the second criterion. Finally, print the corresponding grid solution for the test case.
• When printing the grid solution, do NOT leave blank spaces between each character, nor between each test case
• If there are no solution for a survey response, print -1(-1,-1).
• Implement the functions that you consider necessary to solve the problem.
• Include appropriate comments in your code and a comment header similar to Project 1.

 

Specific Requirements:

 

When coding a program, we try to avoid “Run Errors” using some techniques like checking user input, and some function returns, therefore your program must include the following functionality:

 

• Verify that the command line arguments are at least 2, if not, display an Err Msg, and exitthe program: “Error! You must specify input filename: ./p2 <input_filename>”
• Verify that your program can open the buffer space for a file (fopen), otherwise display an Err Msg, and exitthe program: “Error! The <filename> file can’t be opened”

 

Restrictions:

• Global variables are not allowed

 

Makefile:

 

Create a Makefile to compile your program. Use the template specified in Project 1

 

Submission:

1. On zeus, create a directory named p2_<username>_<labsection>Copy your source file and Makefile to this directory.
2. Create a typescript with the following content:
   1. Show that you are on zeus
   2. Show a listing of your directory
   3. Show your source code
   4. Remove any executable version using Make
   5. Compile the code using Make
   6. Run your program using the input file providing on Blackboard
3. Be sure your directory ONLY contains the source file, typescriptand Makefile
4. Change to the parent directory and create a tarfile of your project directory.

Name this tarfile p2_<username>_<labsection>.tar

5. Submit this tarfileto Blackboard no later than Due Date.