C Programming

This question asks you to implement Jarviss march to compute the convex

hull of a given point set.

Note that if your solution does not implement Jarvis march at all, then up

to only a very small number of marks can possibly be awarded for handling

error cases, no matter whether your program can compute convex hull

correctly or not.

General Requirements: Use a6q1.c as the name of your C source code file.

We will use the following command on bluenose to compile your program:

gcc -std=c99 -o hull a6q1.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:

./hull < a6q1.in.0

In the above command, the file a6q1.in.0 is a plain text file. The first line of this file

is an integer that is the number of points in the point set. Starting from the second

line, 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 can assume

that coordinates are int values.

To simplify your work, you can assume that the x-coordinates of points are distinct,

and the y-coordinates of points are also distinct. You can also assume that no three

points in the point set lie on a single line.

For example, the following file a6q1.in.0 contains a set of points:

4

12

5 19

33 2

-5 88

54 5

12 13

18 39

15 42

17 -5

-3 23

9 29

-8 17

-1 25

Your program should then find the convex hull of these points. It first prints the

number of vertices of the convex hull. It then report the coordinates of these vertices

in clockwise order starting from the topmost vertex. To report a vertex, print its xcoordinate

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

4

-5 88

54 5

17 -5

-8 17

Error Handling: Your program should print an appropriate error message and

terminate in each of the following cases:

(a) The number of points is less than 3 (obviously you need at least 3 points to define

a polygon).

(b) When you try to read an integer from the input file, you encounter an illegal

character. For example, your scanf function encounters a 100 in the input file

and cannot read it as a decimal number.

If there is more than one problem with user input, your program just has to detect one

of them. You can assume that everything else regarding the input file is correct.

Hints:

(a) If you use gdb to debug your program, the following command can run your

program with input redirection (say, the input file is named a6q1.in.0):

run < a6q1.in.0