Find the Closest distance between a pair of point among given n points in Java

In this Java tutorial, we are going to learn how to find the smallest distance between a pair of points in presence of many other points.

Problem statement: Find the closest distance between points in Java

Given points on any plane, you have to find the closest/smallest distance between a pair or between two different points.

Note: The logic for this problem is, first I’m plotting these points and then draw a line between the plane.

Step by Step Approach for this Problem:

1. Sort the given points by their x-coordinates and then split the resulting sorted list into two halves S1 and S2 of size (n/2).
2. By making a recursive call for each of the sets S1 and S2, we have to find the smallest distances d1 and d2 in them. Let = min{d1, d2}.
3. We need to find the closest distance between points from the sets, one point from S1 and one from S2.
4. And check, it is smaller than d or not.
5. To perform that type of check, we have to remove the initial point set and keep only those points whose x-distance to the middle line does not exceed to the d.
6. Now, we have to sort the set of points in the resulting strip by their y-coordinates and scan the resulting list of points.
7. Now, we have to compute for each point that its distance to the seven subsequent points in this list and compute d’, the minimum distance that we encountered during this scan.
8. Finally, we return min{d, d’}.

StringTokenizer class is used here.

You can also learn:

• How to implement an algorithm for the Fractional Knapsack Problem
• How to find Maximum Pairwise Product in Java using Naive approach

Here I’m providing the Java code to get the closest distance between the pair of points:

import java.io.*;
import java.util.*;

import static java.lang.Math.*;

public class Closest {

    static class Point implements Comparable<Point> {
        long x, y;

        public Point(long x, long y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public int compareTo(Point o) {
            return o.y == y ? Long.signum(x - o.x) : Long.signum(y - o.y);
        }
    }

    static double minimalDistance(int[] x, int y[]) {
        double ans = Double.POSITIVE_INFINITY;
        // write your code here
        return ans;
    }

    public static void main(String[] args) throws Exception {
        reader = new BufferedReader(new InputStreamReader(System.in));
        writer = new PrintWriter(System.out);
        int input = nextInt();
        int[] x = new int[input];
        int[] y = new int[input];
        for (int p = 0; p < input; p++) {
            x[p] = nextInt(); // user input
            y[p] = nextInt(); // user input
        }
        System.out.println(minimalDistance(x, y)); //print minimal distance
        writer.close();
    }

    static BufferedReader reader;
    static PrintWriter writer;
    static StringTokenizer tok = new StringTokenizer("");

    static String next() {
        while (!tok.hasMoreTokens()) {
            String w = null;
            try {
                w = reader.readLine();
            } catch (Exception e) {
                e.printStackTrace();
            }
            if (w == null)
                return null;
            tok = new StringTokenizer(w);
        }
        return tok.nextToken();
    }

    static int nextInt() {
        return Integer.parseInt(next());
    }
}

Input

4
7 7   1 100   4 8    7 9

Output

2.00