Your code must make only one call to STL's sort() per convex hull and have overall complexity O(N log N). Everything else is up to you.
Your implementation must show good programming style and be reusable.
Your program must check the following formal condition that addresses all of the above concerns. The distance from the convex hull of the yacht locations to the convex hull of the shark locations should be more than 1 mile. Note that the convex hull includes the interior and the boundary. Therefore, if one convex hull is completely surrounded by the boundary of the other convex hull, the distance between the two hulls is zero.
One potentially helpful fact is that if the two convex hulls are within 1 mile of each other, it is also the case that at least one the points on the boundary of one of the convex hulls is within 1 mile of the other convex hull.
You are to write a program that, given the 2N locations, can determine in O(N log(N)) time whether you should warn all skippers. Your program may terminate as soon as it processed enough data to conclude that the the convex hulls are closer than one mile. For example, when a shark is found half a mile from a yacht, the program may signal "shark-proximity warning" and stop so that all skippers can be warned right away. For complexity analysis, you can assume that the boundary of the convex hulls of both the yachts and sharks contain O(N1/2 ) vertices.
C X Ywhere C is a character (`Y' for Yacht or `S' for shark) and X and Y are real valued coordinates measured in miles. The real numbers will be in the range from -100.0 to 100.0. Having too many lines is not an error, but everything beyond the 2N expected lines should be ignored.
sample input files are available
The command-line argument
-Inputfile will indicate the name of the input file. If no
input file is specified, the file
elvis.txt should be used.
Based on those inputs, your program must generate exactly one of the following messages to standard output:
A shark is too close: 3.4000 -2.4554
A yacht is too close: -8.11 -2.4010
For the first three cases, nothing else should be printed to standard output
and the program must
exit(0). In the case of an error the
program must print an error message to standard output and to the
standard error, then terminate with
It is possible that it may be appropriate to print both message 1 and message 2. However, you are to print out just one of them (your choice).
C X Y" format).
Remember, your implementation should have O(N log(N)) runtime.
worstCase.psin the directory with your program. It should be a one-page graph showing how the run-time varies with N. (The graph must also include your name and unique name!)
runtimeTest.xwhere x varies from 1 to 5. The other five must be non-error test cases which show your program will get the correct answer even for ``corner cases.'' They are to be called
cornerTest.xwhere x again varies from 1 to 5. All of these files should be in a subdirectory named
TESTSand none of these tests should contain more than 10,000 points. Note: for the corner cases you are simply supplying test cases you believe do a good job of testing your code for correctness.
Note that the very operation of receiving data typically takes at least linear time, and N log(N) is a "near-linear" function. Therefore, if your implementation requires O(N log(N)) time, you can say that even in the worst case you can process radar/sonar data almost as fast as they arrive.
More hints will be posted as handouts
makeshould build your program. The command
make cleanshould remove all temporary files and the executable. Your executable should be called
Note that in the overall worst-case, the boundary of the convex hull of N points can contain all of them. However, for the purpose of this project, we assume a "reasonable" distribution with fewer points lying on the boundary of the convex hull. Therefore, we consider worst cases under this assumption.
make cleanactually does remove the executable and the tmp files (such as .o files)
makewill generate an executable called
/afs/engin.umich.edu/class/perm/eecs380/bin/submit380 2 DIRNAME
Also note that if you generate a large number of sharks and a large number of yachts in the square [-100,100]x[-100,100], then most likely, the convex hulls will intersect. You need to come up with ways to generate configurations where convex hulls can be far apart. Otherwise, you will not be able to empirically evaluate worst-case performance and your tests for correctness will be weak.
Finally, you may find it difficult to generate test cases of size N with exactly ceiling(N1/2) vertices in the boundary of the convex hull. Our suggestion is to use a circle and place the needed points on the circle and then place the remaining points well inside of the circle (maintaining the required spacing). This part is not supposed to be hard, if you have problems figuring out how to do it, ask. Discussions (but not code) on this topic are welcome on the newsgroup.
gdb. We've been told that all enrolled 380 students have been given access to Purify. (Thanks Ken!)
These animations (implemented in Java) may illustrate how Graham's scan works...some aren't exactly the same as in the handout (i.e., using the topmost point as P0 instead of the bottommost point, etc.), but they're pretty close:
From Alejo Hausner at Princeton: Graham, Graham Scan
From Mandar Gokhale at U of Illinois: GrahramAlgo
From Connie Peng at U of Maryland (allows you to specify the points): convex hull_anim
Thanks to Brett Allen for finding those.