Implement our O(n log n) algorithm for convex hull computation -- the algorithm from Chapter 1 that sorts points by x-coordinates, and then computes the upper (resp. lower) hull via an incremental algorithm. Your program should read the input from a file called input.txt that is formatted like this example. The first line states the number n of points. Each of the n subsequent lines specifies the index of a point followed by its x and y coordinate. A coordinate of each point is an integer between 0 and 100,000.
The output should be the sequence of indices of those points that occur as vertices of the convex hull. The sequence should begin with the convex hull vertex with the least index, and then report the indices of the vertices as they occur in a counterclockwise traversal of the convex hull boundary. The output should be written to standard output, with the index of one point on each line.
You should submit two things -- the first is your source code, and the second is a file with text on how to compile and/or run your program. Submit to a dropbox in ICON called Homework3
Sunday March 24: I am testing your program on the three files: input0.txt, input1.txt, and a longer input2.txt. For the first two files, the correct output is [3 10 8 14 7 11 4 13]. The second file is basically a scaled and perturbed version of the first to ensure distinct x-coordinates. I don't know the correct output for the third, but I am just using it to check how long your program runs.