Reference no: EM132150489

The task is to implement closest pair algorithm. Along with the implementation in c++, I want two additional things.

Thing 1. Test the correctness of your algorithm in the following way:

Generate 100 random points in the square [0,10]×[0,10] (i.e., the square whose lower-left corner is (0,0) and whose upper-right corner is (10,10)), with the x- and y-coordinates being floats that are chosen randomly and independently.

Compute the minimum distance between these points using your implementation.

Rotate the points counterclockwise 90o around the origin by applying the transformation (x,y)?(-y,x) to all the points, and recompute the minimum distance; it should be the same.

Put your implementation and the code that runs your tests and prints out the results into a single file, closest.cpp, that we can compile and run. Your program should seed the random number generator in such a way that it produces different results each time it is run.

Thing 2. Try to answer the question: what is the expected minimum distance when n random points are chosen in the square [0,10]×[0,10]? Answer this question in the following way:

For each value of n=2, run your algorithm a "bunch" of times with n points, taking the average of the minimum distances that you get, where "a bunch" means enough so that the average pretty much stabilizes,

Make a CSV file with two rows containing your data: on the first row are the values of n, and on the second row are the averages that you got.

Use a spreadsheet program to graph the results.

Make the best guess you can of what function you get; experiment with different functions, seeing how well they fit the graph.

Put your best guess as a text entry on the third line of the CSV file, in the form "f(x) = ...."