Need help with number 2 © Student Home-myFsu × ym2 cop4531.pdf Search Textbook S

Question

Need help with number 2

© Student Home-myFsu × ym2 cop4531.pdf Search Textbook Solutic × e Need Help With 1, Espe X × . C | www.cs.fsu.edu/~tvhoang/classes/Hw2cop453 1.pdf Apps New Tab Online Derivative Ca M ITSDocs: Create, Cop In Unik, how do I list db vi/vim notesIn Unix, how do I cha C-String Password-Introduction to OOP Implementing Sieve Hw2 cop4531.pdf Input Format: The first line contains the size of the aray, namely n. Starting from the second line the array elements are given, one element per e. We provide some sample input and output files, in CI_Input_Output.zip. Below are the details about the input size in the sample files. CI-test 1. txt: n-8; CI-test2.txt: n-432,000; CI-test3.txt: n-25 × 106 Output: The output is an integer representing the total number of inversions in the input array 2. (30 points) Implement Closest Pair of Points. To get full credit, your program should run in O(n log(n) time, as the last test case will be very large. If your program runs with O(n log(n)you will still get 80% credit of this task. Again, britbree implementation shall receive no credit Input: The input is a text file containing the total number of points and the (X,Y) cordinates of all points. Your program will take the file name as an argument, and read it. You can asse that the input has no degeneracy, namely no two points have the same X-coordinate. Input Format: The first line contains the total uumber of points, namely n. Starting from the second line, each line gives the X- and Y-coordinate of a single point, separated by a space. We provide some sample input and out put files, in CP_Input Output.zip. Below are the details about the input size in the sample files CP-test1. txt: n= 5: CP_Teat2.txt: n-1000: CP-teat3. txt: n= 107 Output: The distance between a closest pair 2-1 1 2-2 Homework 2 10/2/2017

Explanation / Answer

Below is the C++ program for finding the distance between closest pair of points The idea is to presort all points according to y coordinates.That saves one iteration to sort, which will lead to O(nLog2n) time. Following is the implementation of O(nLogn) approach. // A divide and conquer program in C++ to find the smallest distance from a // given set of points. #include #include #include #include #include #include using namespace std; // A structure to represent a Point in 2D plane struct Point { int x, y; }; /* Following two functions are needed for library function qsort(). Refer: http://www.cplusplus.com/reference/clibrary/cstdlib/qsort/ */ // Needed to sort array of points according to X coordinate int compareX(const void* a, const void* b) { Point *p1 = (Point *)a, *p2 = (Point *)b; return (p1->x - p2->x); } // Needed to sort array of points according to Y coordinate int compareY(const void* a, const void* b) { Point *p1 = (Point *)a, *p2 = (Point *)b; return (p1->y - p2->y); } // A utility function to find the distance between two points float dist(Point p1, Point p2) { return sqrt( (p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y) ); } // A method to return the smallest distance between two points // in P[] of size n float min_Dist(Point P[], int n) { float min = FLT_MAX; for (int i = 0; i

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

---