ClosestPairPoints.java

ClosestPairPoints.java

import java.util.*;
/*

Distanta minima dintre mai multe puncte

|        
|      x        x
|           x
|          x      x
|              x
|
------------------------------

 
distanta(A,B) = radical((x2-x1)^2 + (y2-y1)^2) 

distanta euclidiana
*/

class Point {
	
	 double x,y;

	 Point(double x, double y) {

	   this.x = x;
	   this.y = y;
	 }
}


class Result {
	
      double distMin;

      Point point1, point2;//Point(abscisa si ordonata)


      Result(double dist, Point pt1, Point pt2) {

          this.distMin = dist;

          this.point1 = pt1;

          this.point2 = pt2;
      }       
}


public class Main {
	

       //distanta Euclidiana
       static double dist(Point p1, Point p2) {

           return Math.sqrt((p2.x-p1.x)*(p2.x-p1.x) + (p2.y-p1.y)*(p2.y-p1.y) );
       }  

       static Result bruteForceClosestPairPoints(List<Point> points) {

              int n = points.size();//cate puncte avem

              double distMin = Double.MAX_VALUE;//valoare mare

              Point X = null, Y = null;

              //Time complexity: O(n^2) 
              for(int i = 0; i < n - 1; ++i) { //merge for-ul pana la penultimul element

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

                          //i = 0; punctul 0 cu celelalte puncte
                          //i = 1; punctul 1 cu restul punctelor ramase

                          double d = dist(points.get( i ), points.get( j ));

                          if(d < distMin) {

                             distMin = d;

                             X = points.get( i );

                             Y = points.get( j );
                          }

                    }

              }

              return new Result(distMin, X, Y);

       }


       public static void main(String[] args) {

         List<Point> points = new ArrayList<>();

         points.add(new Point(1,2)); //i= 0
         points.add(new Point(4,6)); //i = 1
         points.add(new Point(7,1)); //j = i + 1
         points.add(new Point(3,3));
         points.add(new Point(9,5));
         points.add(new Point(2,8));
         points.add(new Point(6,4));
         points.add(new Point(3,7));
         points.add(new Point(8,2));
         points.add(new Point(0,0));

         Result result = bruteForceClosestPairPoints( points );

         System.out.println("Distanta minima =" + result.distMin );
      
         System.out.println("Point1 (" + result.point1.x + ", " + result.point1.y + ")");

         System.out.println("Point2 (" + result.point2.x + ", " + result.point2.y + ")");
       }

}