Cele mai apropiate puncte din plan Complexitate patratica

closest-pair-points.cpp

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

struct Point {

	double x, y;
};

struct Result {
	double dist;
	Point point1;
	Point point2;
};

double dist(Point &point1, Point &point2) {

	   return sqrt((point2.x - point1.x)*(point2.x - point1.x) + (point2.y - point1.y)*(point2.y - point1.y));
}

// 1,2,3,4,5,6,7,8,9,10
//(n-1) + (n-2) + ...+ 1 = n(n-1)/2 = n^2 - n / 2
//Complexitate TIME O(n^2)

Result BruteForceClosestPairPoints(vector<Point> points) {

       int size = points.size();

	   double distMin = 1000000;

	   Point X, Y;

	   //{1,2}, {4,6}, {7,1}, {3,3}, {9,5}, {2,8}, {6,4}, {3,7}, {8,2}, {0,0}
	   //{1,2} {4,6}
	   //{1,2} {7,1}
	   //.....
	   //{1,2) {0,0}
	   //distanta minima

	   //{4,6} {7,1}
	   //{4,6} {3,3}
	   //....
	   //distanta minima

	   //{8,2} {0,0}

       for(int i = 0; i < size - 1; i++) {

       	     for(int j = i + 1; j < size; ++j) {

                      double d = dist(points[i], points[j]);

                      if(d < distMin) {

                           distMin = d;
     
                           X = points[i];

                           Y = points[j];
                      }
       	     }

       }  

       return {distMin, X, Y};
}

int main(int argc, char const *argv[])
{
	
   vector<Point> points = {{1,2}, {4,6}, {7,1}, {3,3}, {9,5}, {2,8}, {6,4}, {3,7}, {8,2}, {0,0}}; 

   Result result = BruteForceClosestPairPoints( points );

   cout<<"Min Dist = "<<result.dist<<endl;

   cout<<"Point1("<<result.point1.x<<","<<result.point1.y<<")\n";

   cout<<"Point2("<<result.point2.x<<","<<result.point2.y<<")\n";
}