CS 302 Assignment 3

Due date: Tuesday, March 1, 2005, midnight

Latest hints added February 22.

Finding the Area of a Convex Hull.
In this assignment, you are to find the area of the convex hull of a finite set of points in the plane. Each point is represented by an ordered pair of numbers, which will be integers just to make it simpler to work with. (The principle is the same if they are arbitrary real numbers.)
Look at the example, or both figures in pdf format.
An of the problem will consists of a single number, which is the number of points in the plane, together with that many ordered pairs of integers, each on a line. For example, the example could have this input.
Your program should read in the points, and compute the convex hull, and then compute the area of the convex hull. The area could either be expressed as a fraction reduced to the lowest terms (or an integer if it's an integer), or a float written to six-place accuracy. For example, this output is correct for the example, and you could write 27.500000 instead of 55/2.
Remember that if a point is on the boundary of the convex hull, it is not necessarily a vertex of the convex hull. For example, if the original set of points is {(0,0),(1,1),(2,2),(2,0)}, then (1,1) is on the boundary of the convex hull, but not a vertex, so it should not be listed in the output.
The output file should list a cycle consisting of all the vertices of the convex hull, starting anywhere, either in clockwise or counter-clockwise order, each point on its own line. The first and last point must be the same. In my example, I start at (8,1) and list them in counter-clockwise order. The last line should contain the area.
Please hand in a listing of all your code, as well as the listings of the output files, regardless of the number of files you need. Each of these files should be emailed separately to the graduate assistant, Rathna Ramaswamy.
Here is another input file.
Here is yet another input file.
Your program must also run correctly on a "secret" input file. You may assume that all integers in the input are in the range -16384 .. 16383.
Some students were trained to break their C++ programs up into multiple files. It really doesn't matter to me, as long as it's all there. But don't put the whole program in one file.
To make things easier on the grader, please include your name as a comment in the program files. Turn in two output files, one for each of the two input files, not counting the first one where I give the answer.
Each output file should also contain your name, which you should type in by hand.
The question of "turning" arose in class, in connection with Graham Scan. Look at this file, or both figures in pdf format. Here is the basic question. If there is an arrow from the point a = (ax,ay) to b = (bx,by) and another arrow from b to c = (cx,cy), does the second arrow "turn right" or "turn left" or "go straight"? (Going backwards in the same line counts as going straight.) The answer can be decided by evaluating the determinant of a 2 by 2 matrix. After cancellation, this determinant has the value:
ax(by -cy) + bx(cy -ay) + cx(ay -by)

Possibly helpful hints: Graham Scan, with a detailed description of the "stack" portion.
Warning: the pseudo-code I am giving you in the hint fails in certain special cases. The failure is not caused by any implementation problem, such as lack of memory, speed, or accuracy, but is an actual flaw in the theory of the code itself, whiich fails to reveal itself except in certain cases which you might not think of at first, but would definitely occur sometimes in some practical applications.
As I told one student yesterday, even if Flash Gordon were running the program on 25th Century computers, Ming the Merciless could come up with (amazingly simple) data that could defeat the algorithm I gave you. You should identify the problem and fix it.

All written assignments must be handwritten (not typed or printed from a computer file) in your own handwriting, on 8.5 by 11 inch paper, or on A4 paper. Write your name on each sheet, and do not fold the pages or crimp the corners. (You may use a paper clip or a staple.)
Turn the pages in to me or to the graduate assistant on the due date.
All programming assignments must be emailed to the graduate assistant, on or before the due date. Your assignments must be emailed from your Engineering College account, and they must run on our computers.
Do not give an electronic copy of your program to any other student. It is a violation of ethics to either turn in another's program or to provide another person with a program to turn in.
If programs from two students are similar, both of them will be under suspicion.