Closest Pair done!

Yay, so much fun. Breaking things down into small, actionable items, and
doing it, this never fails! Persist! Glad that my org-mode Emacs TODO
helps making it happen.

2 files changed, 215 insertions, 0 deletions

diff --git a/AlgoDesignAndTechniqueEdxJava/sources/CloestDistance.java b/AlgoDesignAndTechniqueEdxJava/sources/CloestDistance.java
new file mode 100644
index 0000000..e76768f
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxJava/sources/CloestDistance.java
@@ -0,0 +1,145 @@
+import java.io.BufferedReader;
+import java.io.InputStreamReader;
+import java.io.PrintWriter;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Comparator;
+import java.util.List;
+import java.util.StringTokenizer;
+
+public class CloestDistance {
+
+    public static class Point {
+        long x, y;
+
+        public Point(long x, long y) {
+            this.x = x;
+            this.y = y;
+        }
+    }
+
+    public static class XComparator implements Comparator<Point> {
+
+        @Override
+        public int compare(Point p0, Point p1) {
+            return p0.x == p1.x ? Long.signum(p0.y - p1.y) : Long.signum(p0.x - p1.x);
+        }
+
+    }
+
+    public static class YComparator implements Comparator<Point> {
+
+        @Override
+        public int compare(Point p0, Point p1) {
+            return p0.y == p1.y ? Long.signum(p0.x - p1.x) : Long.signum(p0.y - p1.y);
+        }
+
+    }
+
+    public static double minimalDistance(int[] x, int[] y) {
+        Point[] ptsArray = new Point[x.length];
+
+        for (int i = 0; i < ptsArray.length; i++) {
+            ptsArray[i] = new CloestDistance.Point(x[i], y[i]);
+        }
+
+        Arrays.sort(ptsArray, new CloestDistance.XComparator());
+        return minimalDistance(ptsArray, 0, ptsArray.length - 1);
+    }
+
+    private static double minimalDistance(Point[] ptsArray, int low, int high) {
+        if (high - low <= 3) {
+            return baseCaseMinDistance(ptsArray, low, high);
+        }
+        int mid = low + (high - low) / 2;
+        long midX = ptsArray[mid].x;
+        double d1 = minimalDistance(ptsArray, low, mid - 1);
+        double d2 = minimalDistance(ptsArray, mid, high);
+        double d = Math.min(d1, d2);
+        List<Point> shadedPoints = new ArrayList<Point>();
+        for (int i = low; i <= high; i++) {
+            if (Math.abs(ptsArray[i].x - midX) <= d)
+                shadedPoints.add(ptsArray[i]);
+        }
+
+        shadedPoints.sort(new YComparator());
+
+        double dPrime = dPrimeDistance(shadedPoints);
+
+        return Math.min(d, dPrime);
+    }
+
+    private static double dPrimeDistance(List<Point> shadedPoints) {
+        double minDistance = Double.MAX_VALUE;
+        double tempDistance;
+        for (int i = 0; i < shadedPoints.size(); i++) {
+            for (int j = 1; j <= 7; j++) {
+                if (i + j < shadedPoints.size()) {
+                    tempDistance = distance(shadedPoints.get(i), shadedPoints.get(i + j));
+                    minDistance = Math.min(tempDistance, minDistance);
+                }
+            }
+        }
+        return minDistance;
+    }
+
+    private static double baseCaseMinDistance(Point[] ptsArray, int low, int high) {
+        if (high - low == 1)
+            return distance(ptsArray[low], ptsArray[high]);
+        if (high - low == 2) {
+            double d1 = distance(ptsArray[low], ptsArray[low + 1]);
+            double d2 = distance(ptsArray[low], ptsArray[high]);
+            double d3 = distance(ptsArray[high], ptsArray[low + 1]);
+            return Math.min(d1, Math.min(d2, d3));
+        }
+        double d1 = distance(ptsArray[low], ptsArray[low + 1]);
+        double d2 = distance(ptsArray[low], ptsArray[low + 2]);
+        double d3 = distance(ptsArray[low], ptsArray[high]);
+        double d4 = distance(ptsArray[low + 1], ptsArray[low + 2]);
+        double d5 = distance(ptsArray[low + 1], ptsArray[high]);
+        double d6 = distance(ptsArray[low + 2], ptsArray[high]);
+        return Math.min(d1, Math.min(d2, Math.min(d3, Math.min(d4, Math.min(d5, d6)))));
+    }
+
+    public static double distance(Point p1, Point p2) {
+        return Math.sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
+    }
+
+    public static void main(String[] args) throws Exception {
+        reader = new BufferedReader(new InputStreamReader(System.in));
+        writer = new PrintWriter(System.out);
+        int n = nextInt();
+        int[] x = new int[n];
+        int[] y = new int[n];
+        for (int i = 0; i < n; i++) {
+            x[i] = nextInt();
+            y[i] = nextInt();
+        }
+        System.out.println(minimalDistance(x, y));
+        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());
+    }
+}
\ No newline at end of file
diff --git a/AlgoDesignAndTechniqueEdxJava/tests/ClosestDistanceTest.java b/AlgoDesignAndTechniqueEdxJava/tests/ClosestDistanceTest.java
new file mode 100644
index 0000000..87ce590
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxJava/tests/ClosestDistanceTest.java
@@ -0,0 +1,70 @@
+import static org.junit.jupiter.api.Assertions.*;
+
+import java.util.Arrays;
+
+import org.junit.jupiter.api.Test;
+
+class ClosestDistanceTest {
+
+    @Test
+    void test() {
+        int[] x = { 0, 3 };
+        int[] y = { 0, 4 };
+        double result = 5.0;
+        assertEquals(result, CloestDistance.minimalDistance(x, y), 0.0001);
+    }
+
+    @Test
+    void testThreePoints() {
+        int[] x = { 0, 3, 5 };
+        int[] y = { 0, 4, 6 };
+        double result = 2.828427;
+        assertEquals(result, CloestDistance.minimalDistance(x, y), 0.0001);
+    }
+
+    @Test
+    void test1() {
+        int[] x = { 7, 1, 4, 7 };
+        int[] y = { 7, 100, 8, 7 };
+        double result = 0.0;
+        assertEquals(result, CloestDistance.minimalDistance(x, y), 0.0001);
+    }
+
+    @Test
+    void test2() {
+        int[] x = { 4, -2, -3, -1, 2, -4, 1, -1, 3, -4, -2 };
+        int[] y = { 4, -2, -4, 3, 3, 0, 1, -1, -1, 2, 4 };
+        double result = 1.414213;
+        assertEquals(result, CloestDistance.minimalDistance(x, y), 0.0001);
+    }
+
+    @Test
+    void testSortPointsArray() {
+        int[] x = { 4, -2, -3, -1, 2, -4, 1, -1, 3, -4, -2 };
+        int[] y = { 4, -2, -4, 3, 3, 0, 1, -1, -1, 2, 4 };
+        CloestDistance.Point[] p = new CloestDistance.Point[11];
+        for (int i = 0; i < p.length; i++) {
+            p[i] = new CloestDistance.Point(x[i], y[i]);
+        }
+
+        Arrays.sort(p, new CloestDistance.XComparator());
+        assertEquals(-4, p[0].x);
+        assertEquals(0, p[0].y);
+
+        Arrays.sort(p, new CloestDistance.YComparator());
+        assertEquals(-4, p[0].y);
+        assertEquals(-3, p[0].x);
+        assertEquals(4, p[10].y);
+        assertEquals(4, p[10].x);
+
+    }
+
+    @Test
+    void testDistance() {
+        CloestDistance.Point p1 = new CloestDistance.Point(0, 0);
+        CloestDistance.Point p2 = new CloestDistance.Point(1, 1);
+        double result = 1.414213;
+        assertEquals(result, CloestDistance.distance(p1, p2), 0.0001);
+    }
+
+}