Background: This problem asks you to compute the convex hull of a point set. This is a fundamental problem in computational geometry, and it has many applications in GIS and graphics applications. It is even used in software that many of you have tried before. Think of a vector graphics editor or even the feature of drawing objects in Powerpoint. These programs often let you group shapes (polygons, line segments, etc.) that you draw as one entity. Then, you can click on any shape in this group to move the entire group around. How does the software detect whether you clicks over any shape in this group? One common solution is to compute the convex hull of this group, and then the software simply tests whether you clicks inside the convex hull (which is a convex polygon as we will see soon), and this can be done very efficiently. As some background knowledge in geometry and how to perform computations in geo- metric data sets efficiently is required, the first part of the assignment is focused on such background knowledge, before the problem specifications of the programming questions.

Properties of directed line segments: Recall (from what you have learned in geometry lessons before) that a line segment is a part of a line that is bounded by two distinct end points and contains every point on the line between these two end points. A directed line segment is a line segment endowed with the additional property of direction. Let p1 = (x1, y1) and p2 = (x2, y2) be two distinct points on the plane. That is, (x1, y1) is the coordinates of p1 and (x2, y2) is the coordinates of p2. We then use p1p2 to represent the directed line segment from p1 to p2. Given two directed line segments that share the starting endpoint, a useful operation is to determine which line segment is clockwise from the other. More precisely, we are given three points p0 = (x0, y0), p1 = (x1, y1) and p2 = (x2, y2), and these three points do not lie on a single straight line. We would like to find out whether p0p1 is clockwise or counterclockwise from p0p2. That is, if we would like to turn p0p2 by less than 180 degrees toward p0p1, so that they will align, should we turn clockwise, or counterclockwise? Figure 1 gives two examples. In the first example, p0p1 is clockwise from p0p2. In the second example, p0p1 is counterclockwise from p0p2. To find this out, we evaluate the following expression:

If the result is positive, then p0p1 is clockwise from p0p2. If negative, it is counterclockwise. This approach is based on cross products. Here I simply gave you the formula, and if you are interested, you could do some research to learn more about cross products. This approach is cool because it does not require division at all. This is desired as divisions are typically slower than addition, subtraction or multiplication on most CPUs, and to perform division, we also need avoid division by zero.

Convex Hull: For a given point set P, its convex hull is the smallest convex polygon C for which each point in P is either inside C or on the boundary of C. Figure 2 gives an example. In this example, P = {p0, p1, p2, p3, p4, p5, p6, p7}. The convex hull of P is the convex polygon defined by p2, p4, p3, p6 and p7. How to compute the convex hull efficiently? There are many algorithms and here you are asked to implement an algorithm called Jarviss march. To introduce this algorithm, we will assume that the x-coordinates of points are distinct, and the y-coordinates of points are also distinct. We will also assume that no three points in the point set lie on a single line. Take Figure 2 as an example. It is clear that the point with the largest y-coordinate (p2 in this example) is one of the vertices of the convex hull. Then, use a pencil to draw directed line segments p2p0, p2p1, p2p3, , p2p7 (Be sure to do this yourself). We know that p4 is the vertex next to p2 on the convex hull in clockwise order. What is special about p2p4 among all the line segments that we drew? I will give the answer in the next paragraph; think about this yourself for a while to see if you can find this out by yourself. What is special about p2p4 is that it is counterclockwise from any other directed line segment that we drew. Now, consider the point p4 which is the next vertex on the convex hull after p2 in clockwise order. We first erase the line segments that we drew before, and then draw all the direct lines segments p4p0, p4p1, p4p3, p4p5, p4p6, p2p7. We can observe the same property for p4p3, which leads to the next vertex p3. We can repeat this process until we are back at vertex p2. By now we have computed the convex hull. Jarviss march is based on this idea. The following is the pseudocode that computes the convex hull, C, of the point set S = {p0, , pn1}:

1. 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 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

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:

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 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

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 a100 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.

P2 p2 Pi clockwise counterclockwise Po Figure 1: Clockwise vs Counterclockwise