Implement the Divide and Conquer based 2D Convex Hull computing algorithm discussed in class. Use the LeftOf test during the merge process.

The input to your program should be a plain ASCII file containing (x, y) coordinates of one point per line. The first line of the file will contain the number of points. For instance, 5 0 0 1 1 2 3 3 4 4 5

The output will consist of the vertices (extreme points) comprising the convex hull, in clockwise order. Each line will contain the (x, y) coordinates of the vertex. The first line of the line will contain the number of vertices in the convex hull. For instance, 4 0 0 2 3 4 5 1 1

Submission consists of 1. A five-page report containing (i) pseudo-code of the algorithm implemented, (ii) five example cases, some of which should include some special case conditions, of convex hull computed by the code, (iii) a plot of the time taken to execute the code versus the number of input points. Vary the number of points until your code takes about a minute to compute. Plot the best fitting polynomial to the points. Comment on the shape. 2. Your source code 3. A demo of your code on sample inputs. You will setup demo time with the TA during his office to demo the code. He will share a signup schedule.