My code works for number 2 which will give me the correct answer when I have a s
ID: 3587559 • Letter: M
Question
My code works for number 2 which will give me the correct answer when I have a small input file but when I try it with an input file that has a really large amount of coordinates like 1000+ It doesnt work. I've narrowed it down to the problem being in the float closestUtil(Point Px[], Point Py[], int n) function but I still cant figure it out.
My code (in C++):
#include
#include
#include
#include
#include
#include
using namespace std;
// A structure to represent a Point in 2D plane
struct Point
{
float x, y;
};
// 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;
}
float stripClosest(Point strip[], int size, float d)
{
float min = d; // Initialize the minimum distance as d
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;
}
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 = new Point[mid+1]; // y sorted points on left of vertical line ////Point *Pyl = new Point[mid+1]
Point *Pyr = new Point[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 = new Point[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 = new Point[n]; //////
Point *Py = new Point[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()
{
string file;
cout << "Enter Input File Name : ";
cin >> file;
ifstream in1(file);
int i = 0, x, y;
if (in1.is_open())
{
int n;
in1 >> n;
cout << n << endl;
Point *P = new Point[n]; //Struct array to hold points
for(int i = 0; i < n; i++)
{
in1 >> P[i].x;
in1 >> P[i].y;
cout << P[i].x << ", " << P[i].y << endl;
}
cout << "The Closest distance is " << closest(P, n);
}
in1.close();
return 0;
}
© 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/2017Explanation / Answer
NOTE Since time complexity of this is n(logn)(logn) which is little high so I have tried optimize it now as for my end this program is working fine also in /////////////////////////////////////////////////////////////////////
float stripClosest(Point strip[], int size, float d)
{
float min = d; // Initialize the minimum distance as d
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]);
}
}///////////////////////////////////////////////////////////////////// this part you have to sort strip which was missing
#include <bits/stdc++.h>
#include<iostream>
using namespace std;
// A structure to represent a Point in 2D plane
struct Point
{
float x, y;
};
// 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;
}
/*float stripClosest(Point strip[], int size, float d)
{
float min = d; // Initialize the minimum distance as d
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;
}*/
float stripClosest(Point strip[], int size, float d)
{
float min = d; // Initialize the minimum distance as d
qsort(strip, size, sizeof(Point), compareY);
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;
}
/*float closestUtil(Point Px[], Point Py[], int n)
no need of py[] as arguement*/
float closestUtil( Point Py[], int n)
{
if (n <= 3)
return min_Dist(Py, n);
// Find the middle point
int mid = n/2;
Point midPoint = Py[mid];
// Divide points in y sorted array around the vertical line.
// Assumption: All x coordinates are distinct.
Point *Pyl = new Point[mid+1]; // y sorted points on left of vertical line ////Point *Pyl = new Point[mid+1]
Point *Pyr = new Point[n-mid-1]; // y sorted points on right of vertical line ////
int li = 0, ri = 0; // indexes of left and right subarrays
/*this increses the time complexity
/*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(Py, mid);
float dr = closestUtil( Py+mid, 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 = new Point[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 = new Point[n]; //////
Point *Py = new Point[n]; /////
for (int i = 0; i < n; i++)
{
Px[i] = P[i];
Py[i] = P[i];
}
//qsort(Px, n, sizeof(Point), compareX); no need
qsort(Py, n, sizeof(Point), compareX);
// Use recursive function closestUtil() to find the smallest distance
return closestUtil( Py, n);
}
// Driver program to test above functions
int main()
{
string file;
cout << "Enter Input File Name : ";
cin >> file;
ifstream in1(file);
int i = 0, x, y;
if (in1.is_open())
{
int n;
in1 >> n;
cout << n << endl;
Point *P = new Point[n]; //Struct array to hold points
for(int i = 0; i < n; i++)
{
in1 >> P[i].x;
in1 >> P[i].y;
cout << P[i].x << ", " << P[i].y << endl;
}
cout << "The Closest distance is " << closest(P, n);
}
in1.close();
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.