summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--AlgoDesignAndTechniqueEdxJava/sources/CloestDistance.java145
-rw-r--r--AlgoDesignAndTechniqueEdxJava/tests/ClosestDistanceTest.java70
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);
+ }
+
+}