CSC 269 Programming Project
Finding the Area of the Convex Hull
Due Thursday August 1, 2002

• If you use "off the shelf" code from any source, please cite the source.
• Write a program that computes the area of the convex hull of a finite set of points in the plane. points.
• The input file of your program will be a text file containing any number lines, each line containing the x and y coordinates of a point in the plane. The points are listed in arbitrary order, and there may be duplicates.
  The convex hull of a set S is defined to be the minimal convex set K which contains S. If S is finite, K will be a polyhedron, together with its interior.
• I don't want to spoil your fun by giving away too much. But, if you are totally stuck, here is a hint.
• Here are some files for testing your program:
  points01
  points02
  points03
• The running time of the program should be O(n log n), where n is the number of points in S.
• It took me 114 minutes (counting interruptions) to write the program.
• The following lines are from the running of my program using points01:
  upper:
  1 2
  2 8
  5 3
  lower:
  1 2
  5 3
  Area = 11.5