C program:

Background: A point (x1, y1) is said to dominate another point (x2, y2) in the plane if both x1 >= x2 and y1 >= y2 hold. For example, (5, 2) dominates (3, 1), but neither of the two points (3, 2) or (2, 5) dominates the other. A point p is a maximal point of a point set S if there does not exist another point in S that dominates p.

The problem: In this question, you are asked to write a C program based on sorting that reports all the maximal points in a given point set. Note that this problem is useful for the support of certain new features of SQL (structured query language) for database systems.

How do we solve this problem? One of the most efficient solutions makes use of an algorithm design paradigm called reducing to known problems. Informally speaking, this paradigm means that when we encounter a new problem, we can try to solve it by making use of solutions to other problems that we already know how to solve.

The problem of finding all the maximal points can be solved by making use of solutions to the sorting problem. To see this, first sort all the points by x-coordinates in ascending order. Then, check all the points from right to left. Think of this question: What points should you report? I will state the answer in the next paragraph; I would however suggest you to try to figure out how by yourself first and then read the next paragraph to confirm whether your own solution is correct.

Here is the solution: sort all the points in ascending order by x-coordinate. Then check the points one by one from right to left, recording the largest y-coordinate seen so far. For each point, if its y-coordinate is larger than the largest y-coordinate of all the points to its right, report it as a maximal point. Note that the rightmost point is always a maximal point. Draw a figure yourself to see the correctness. To simplify your work, you can assume that x-coordinates are distinct.

You are asked to implement this solution. In your implementation, you can use any reasonable sorting algorithm including insertion sort and bubble sort (though you should know why they are not as efficient as better solutions), and you will not lose any marks if you do not implement the most efficient sorting algorithms. You are forbidden to use any existing C library functions that can be used to sort an array, such as qsort. You will lose a lot of marks if you do so.

No marks will be given if your solution is not based on sorting as specified above.

General Requirements: Use a5q2.c as the name of your C source code file. We will use the following command to compile your program:

gcc -std=c99 -o max a5q2.c

As many numbers have to be read from stdin to test your program, you are expected to use input redirection to read the input from a file. More precisely, you can run your program using the following command:

./max < max.in.0

In the above command, the file max.in.0 is a plain text file that contains the coordinates of exactly ten points. This file has exactly ten lines, and each line contains two integers. The first integer is the x-coordinate of a point, and the second integer is its y-coordinate. Hence, in this question, you just have to handle point sets of size 10 and you can assume that coordinates are int values.

For example, the following file max.in.0 contains coordinates of 10 points:

12 5 29 7 0 13 55 9 47 2 23 -5 -7 90 11 33 25 -24 21 7

Your program should then find the maximal points among these 10 points, and report the maximal points in decreasing order of x-coordinates. To report a point, print its x-coordinate and y-coordinate in a single line, use exactly one space between these two values (this is the only space character in this line), and terminate this line with a newline character. For example, the output of the above example is expected to be

55 9 11 33 -7 9