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
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 < n; ++i) for (int j = i+1; j < n; ++j) if (dist(P[i], P[j]) < min) min = dist(P[i], P[j]); return min; } // A utility function to find minimum of two float values float min(float x, float y) { return (x < y)? x : y; } // A utility function to find the distance beween the closest points of // strip of given size. All points in strip[] are sorted accordint to // y coordinate. They all have an upper bound on minimum distance as d. // Note that this method seems to be a O(n^2) method, but it\'s a O(n) // method as the inner loop runs at most 6 times float stripClosest(Point strip[], int size, float d) { float min = d; // Initialize the minimum distance as d // Pick all points one by one and try the next points till the difference // between y coordinates is smaller than d. // This is a proven fact that this loop runs at most 6 times for (int i = 0; i < size; ++i) for (int j = i+1; j < size && (strip[j].y - strip[i].y) < min; ++j) if (dist(strip[i],strip[j]) < min) min = dist(strip[i], strip[j]); return min; } // A recursive function to find the smallest distance. The array Px contains // all points sorted according to x coordinates and Py contains all points // sorted according to y coordinates float closestUtil(Point Px[], Point Py[], int n) { if (n <= 3) return min_Dist(Px, n); // Find the middle point int mid = n/2; Point midPoint = Px[mid]; // Divide points in y sorted array around the vertical line. // Assumption: All x coordinates are distinct. Point Pyl[mid+1]; // y sorted points on left of vertical line Point Pyr[n-mid-1]; // y sorted points on right of vertical line int li = 0, ri = 0; // indexes of left and right subarrays for (int i = 0; i < n; i++) { if (Py[i].x <= midPoint.x) Pyl[li++] = Py[i]; else Pyr[ri++] = Py[i]; } // Consider the vertical line passing through the middle point // calculate the smallest distance dl on left of middle point and // dr on right side float dl = closestUtil(Px, Pyl, mid); float dr = closestUtil(Px + mid, Pyr, n-mid); // Find the smaller of two distances float d = min(dl, dr); // Build an array strip[] that contains points close (closer than d) // to the line passing through the middle point Point strip[n]; int j = 0; for (int i = 0; i < n; i++) if (abs(Py[i].x - midPoint.x) < d) strip[j] = Py[i], j++; // Find the closest points in strip. Return the minimum of d and closest // distance is strip[] return min(d, stripClosest(strip, j, d) ); } // The main functin that finds the smallest distance // This method mainly uses closestUtil() float closest(Point P[], int n) { Point Px[n]; Point Py[n]; for (int i = 0; i < n; i++) { Px[i] = P[i]; Py[i] = P[i]; } qsort(Px, n, sizeof(Point), compareX); qsort(Py, n, sizeof(Point), compareY); // Use recursive function closestUtil() to find the smallest distance return closestUtil(Px, Py, n); } // Driver program to test above functions int main() { int n, i=0, x, y; Point P[n] ; //Struct array to hold points //open input file..import ifsteam and sstream ifstream inputFile(\"CP_test1.txt\"); //replace your file to Test string line; while (getline(inputFile, line)) //Read the file line by line { if(line.find(\"n\")==0) //if the line contains \"n\" { string string1,string2,string3; istringstream stringstream(line); //pass the line in stringstream stringstream >> string1 >> string2 >> string3; //store n, = and the number in //seperate strings istringstream stringstream(string3); stringstream >> n; //To convert string to int } else { //To retrieve x and y coordinates string stringX,stringY; istringstream stringstream(line); //pass the line in stringstream stringstream >> stringX >> stringY; //Read x and y //To convert string to int istringstream stringstream(stringX); stringstream >> x; istringstream stringstream(stringY); stringstream >> y; P[i] = {x, y}; //Store x and y in P[i] i++; } } cout << \"The Closest distance is \" << closest(P, n); return 0; }
Homework Sourse