fork download
copy 
  1. // A divide and conquer program in C/C++ to find the smallest distance from a
  2. // given set of points.
  3.  
  4. #include <iostream> 
  5. #include <stdio.h>
  6. #include <float.h>
  7. #include <stdlib.h>
  8. #include <math.h>
  9. #include <iomanip>
  10. using namespace std;
  11.  
  12. // A structure to represent a Point in 2D plane
  13. struct Point
  14. {
  15.     int x, y;
  16. };
  17.  
  18. Point p1,p2;
  19.  
  20. /* Following two functions are needed for library function qsort().
  21.    Refer: http://w...content-available-to-author-only...s.com/reference/clibrary/cstdlib/qsort/ */
  22.  
  23. // Needed to sort array of points according to X coordinate
  24. int compareX(const void* a, const void* b)
  25. {
  26.     Point *p1 = (Point *)a,  *p2 = (Point *)b;
  27.     return (p1->x - p2->x);
  28. }
  29. // Needed to sort array of points according to Y coordinate
  30. int compareY(const void* a, const void* b)
  31. {
  32.     Point *p1 = (Point *)a,   *p2 = (Point *)b;
  33.     return (p1->y - p2->y);
  34. }
  35.  
  36. // A utility function to find the distance between two points
  37. float dist(Point p1, Point p2)
  38. {
  39.     return sqrt( (p1.x - p2.x)*(p1.x - p2.x) +
  40.                  (p1.y - p2.y)*(p1.y - p2.y)
  41.                );
  42. }
  43.  
  44. // A Brute Force method to return the smallest distance between two points
  45. // in P[] of size n
  46. float bruteForce(Point P[], int n)
  47. {
  48.     float min = FLT_MAX;
  49.     for (int i = 0; i < n; ++i)
  50.         for (int j = i+1; j < n; ++j)
  51.             if (dist(P[i], P[j]) < min)
  52.             	{
  53.                 min = dist(P[i], P[j]);
  54.                 p1=P[i];
  55.                 p2=P[j];
  56.             	}
  57.     return min;
  58. }
  59.  
  60. // A utility function to find minimum of two float values
  61. float min(float x, float y)
  62. {
  63.     return (x < y)? x : y;
  64. }
  65.  
  66.  
  67. // A utility function to find the distance beween the closest points of
  68. // strip of given size. All points in strip[] are sorted accordint to
  69. // y coordinate. They all have an upper bound on minimum distance as d.
  70. // Note that this method seems to be a O(n^2) method, but it's a O(n)
  71. // method as the inner loop runs at most 6 times
  72. float stripClosest(Point strip[], int size, float d)
  73. {
  74.     float min = d;  // Initialize the minimum distance as d
  75.  
  76.     qsort(strip, size, sizeof(Point), compareY); 
  77.  
  78.     // Pick all points one by one and try the next points till the difference
  79.     // between y coordinates is smaller than d.
  80.     // This is a proven fact that this loop runs at most 6 times
  81.     for (int i = 0; i < size; ++i)
  82.         for (int j = i+1; j < size && (strip[j].y - strip[i].y) < min; ++j)
  83.             if (dist(strip[i],strip[j]) < min)
  84.             	{
  85.                 min = dist(strip[i], strip[j]);
  86.                 p1=strip[i];
  87.                 p2=strip[j];
  88.             	}
  89.  
  90.     return min;
  91. }
  92.  
  93. // A recursive function to find the smallest distance. The array P contains
  94. // all points sorted according to x coordinate
  95. float closestUtil(Point P[], int n)
  96. {
  97.     // If there are 2 or 3 points, then use brute force
  98.     if (n <= 3)
  99.         return bruteForce(P, n);
  100.  
  101.     // Find the middle point
  102.     int mid = n/2;
  103.     Point midPoint = P[mid];
  104.  
  105.     // Consider the vertical line passing through the middle point
  106.     // calculate the smallest distance dl on left of middle point and
  107.     // dr on right side
  108.     float dl = closestUtil(P, mid);
  109.     float dr = closestUtil(P + mid, n-mid);
  110.  
  111.     // Find the smaller of two distances
  112.     float d = min(dl, dr);
  113.  
  114.     // Build an array strip[] that contains points close (closer than d)
  115.     // to the line passing through the middle point
  116.     Point strip[n];
  117.     int j = 0;
  118.     for (int i = 0; i < n; i++)
  119.         if (abs(P[i].x - midPoint.x) < d)
  120.             strip[j] = P[i], j++;
  121.  
  122.     // Find the closest points in strip.  Return the minimum of d and closest
  123.     // distance is strip[]
  124.     return min(d, stripClosest(strip, j, d) );
  125. }
  126.  
  127. // The main functin that finds the smallest distance
  128. // This method mainly uses closestUtil()
  129. float closest(Point P[], int n)
  130. {
  131.     qsort(P, n, sizeof(Point), compareX);
  132.  
  133.     // Use recursive function closestUtil() to find the smallest distance
  134.     return closestUtil(P, n);
  135. }
  136.  
  137. // Driver program to test above functions
  138. int main()
  139. {
  140.    Point P[50005],X[50005];
  141.     int n;
  142.     cin>>n;
  143.     for(int i=0;i<n;i++)
  144.     	{
  145.     	cin>>P[i].x>>P[i].y;
  146.     	X[i]=P[i];
  147.     	}
  148.  
  149.     qsort(P, n, sizeof(Point), compareX);
  150.  
  151. 	double wynik=closestUtil(P, n);
  152. 	//cout<<"("<<p1.x<<" "<<p1.y<<"),("<<p2.x<<" "<<p2.y<<endl;
  153.     int i,j;
  154.     for(int k=0;k<n;k++)
  155.     	{
  156.     	if(p1.x==X[k].x&&p1.y==X[k].y)i=k;
  157.     	if(p2.x==X[k].x&&p2.y==X[k].y)j=k;
  158.     	}
  159.     cout<<min(i,j)<<" "<<max(i,j)<<" "<<fixed<<setprecision(6)<<wynik; 
  160. }
Success #stdin #stdout 0s 4392KB
comments (?)
stdin
copy 
5
0 0
0 1
1 0
-1 0
0 -1
stdout
copy 
1 2 1.000000
https://ideone.com/XgVBHY
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!