diff options
| -rw-r--r-- | AlgoDesignAndTechniqueEdxJava/sources/CloestDistance.java | 145 | ||||
| -rw-r--r-- | AlgoDesignAndTechniqueEdxJava/tests/ClosestDistanceTest.java | 70 |
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); + } + +} |