import java.util.Scanner; import java.util.ArrayList; import java.lang.Math; public class ClosestPair { private static Scanner in; private static double s; public static void main(String[] args) { in = new Scanner(System.in); s = ((double)in.nextInt()) / ((double)in.nextInt()); int N = in.nextInt(); ArrayList pointX = new ArrayList(); ArrayList pointY = new ArrayList(); for (int i = 0; i < N; i++) { pointX.add(in.nextInt()); pointY.add(in.nextInt()); } // The 'cutting boxes' part actually consists of computing // the so-called Split Tree. You can do this in O(n log n) // time using a complicated procedure; the method used in this // exercise have a O(n^2) worst case on weird point sets. int[] splitTree = computeSplitTree(pointX, pointY); // The 'far apart' pairs are normally called 'well-separated' pairs. // Parts 2 and 3 actually compute the so called Well-Separated // Pair Decomposition, or WSPD for short. // The reason it is called a 'decomposition' is because for // every two points a and b, there is some pair A and B such that // a is in A and b is in B. // Better yet, you can prove that the procedure computes only // a linear number of well-separated pairs, which is better than // the quadratic number of distances (there are n(n-1)/2 distances). // Best of all, the procedure also works for higher dimensions, // and you still have a linear number of pairs and an O(n log n) // running time. Finding the shortest distance can therefore be done // in O(n log n) time for arbitrary dimensions quite easily // (there is another way of doing that, but it's complicated). // The WSPD is useful for a million more things (all more complicated // than computing the shortest distance); do the course // Geometric Algorithms in your forth year for another example // (provided the contents of the course don't change). computeWspd(splitTree); System.out.println(shortestDistance); } private static final int LEFT = 0; private static final int RIGHT = 1; private static final int TOP = 2; private static final int BOTTOM = 3; private static final int BOUNDING_BOX_SIZE = 4; private static int[] getBoundingBox(ArrayList pointX, ArrayList pointY) { int left = pointX.get(0); int right = pointX.get(0); int top = pointY.get(0); int bottom = pointY.get(0); for (int i = 0; i < pointX.size(); i++) { if (left > pointX.get(i)) left = pointX.get(i); if (right < pointX.get(i)) right = pointX.get(i); if (bottom > pointY.get(i)) bottom = pointY.get(i); if (top < pointY.get(i)) top = pointY.get(i); } int[] result = new int[BOUNDING_BOX_SIZE]; result[LEFT] = left; result[RIGHT] = right; result[TOP] = top; result[BOTTOM] = bottom; return result; } private static boolean leftRightSplit(int[] boundingBox) { return boundingBox[RIGHT] - boundingBox[LEFT] >= boundingBox[TOP] - boundingBox[BOTTOM]; } private static double leftRightMean(int[] boundingBox) { return (double)(boundingBox[RIGHT] + boundingBox[LEFT]) / 2.0; } private static double topBottomMean(int[] boundingBox) { return (double)(boundingBox[TOP] + boundingBox[BOTTOM]) / 2.0; } private static double distance(double x1, double y1, double x2, double y2) { double dx = x2 - x1; double dy = y2 - y1; return Math.sqrt(dx * dx + dy * dy); } private static double size(int[] boundingBox) { return distance(boundingBox[LEFT], boundingBox[BOTTOM], leftRightMean(boundingBox), topBottomMean(boundingBox)); } private static boolean areWellSeparated(int[] boundingBox1, int[] boundingBox2) { double R = Math.max(size(boundingBox1), size(boundingBox2)); return distance(leftRightMean(boundingBox1), topBottomMean(boundingBox1), leftRightMean(boundingBox2), topBottomMean(boundingBox2)) >= (s + 2) * R; } private static double longest(int[] boundingBox) { return Math.max(boundingBox[RIGHT] - boundingBox[LEFT], boundingBox[TOP] - boundingBox[BOTTOM]); } private static ArrayList splitTreeNodes = new ArrayList(); private static ArrayList boundingBoxes = new ArrayList(); private static final int LEFT_NODE = 0; private static final int RIGHT_NODE = 1; private static final int X_COORDS = 2; private static final int Y_COORDS = 3; private static final int BOUNDING_BOX = 4; private static final int INDEX = 5; private static final int SPLIT_NODE_SIZE = 6; private static ArrayList> coordinateLists = new ArrayList>(); private static int[] computeSplitTree(ArrayList pointX, ArrayList pointY) { if (pointX.size() > 1) { int[] boundingBox = getBoundingBox(pointX, pointY); ArrayList pointXLeft = new ArrayList(); ArrayList pointYLeft = new ArrayList(); ArrayList pointXRight = new ArrayList(); ArrayList pointYRight = new ArrayList(); splitLeftRight(pointX, pointY, pointXLeft, pointYLeft, pointXRight, pointYRight, boundingBox); System.out.println(pointXLeft.size()); int[] leftNode = computeSplitTree(pointXLeft, pointYLeft); int[] rightNode = computeSplitTree(pointXRight, pointYRight); return createSplitNode(leftNode[INDEX], rightNode[INDEX], pointX, pointY, boundingBox); } else { printPoint(pointX.get(0), pointY.get(0)); int[] boundingBox = getBoundingBox(pointX, pointY); return createSplitNode(-1, -1, pointX, pointY, boundingBox); } } private static void splitLeftRight(ArrayList pointX, ArrayList pointY, ArrayList pointXLeft, ArrayList pointYLeft, ArrayList pointXRight, ArrayList pointYRight, int[] boundingBox) { for (int i = 0; i < pointX.size(); i++) { if (leftRightSplit(boundingBox)) { if (pointX.get(i) <= leftRightMean(boundingBox)) { pointXLeft.add(pointX.get(i)); pointYLeft.add(pointY.get(i)); } else { pointXRight.add(pointX.get(i)); pointYRight.add(pointY.get(i)); } } else { if (pointY.get(i) <= topBottomMean(boundingBox)) { pointXLeft.add(pointX.get(i)); pointYLeft.add(pointY.get(i)); } else { pointXRight.add(pointX.get(i)); pointYRight.add(pointY.get(i)); } } } } private static int[] createSplitNode(int leftNode, int rightNode, ArrayList pointX, ArrayList pointY, int[] boundingBox) { int[] splitNode = new int[SPLIT_NODE_SIZE]; splitNode[LEFT_NODE] = leftNode; splitNode[RIGHT_NODE] = rightNode; splitNode[X_COORDS] = coordinateLists.size(); coordinateLists.add(pointX); splitNode[Y_COORDS] = coordinateLists.size(); coordinateLists.add(pointY); splitNode[BOUNDING_BOX] = boundingBoxes.size(); boundingBoxes.add(boundingBox); splitNode[INDEX] = splitTreeNodes.size(); splitTreeNodes.add(splitNode); return splitNode; } private static void printPoint(int x, int y) { System.out.print(x); System.out.print(" "); System.out.println(y); } private static void computeWspd(int[] splitTree) { if (splitTree[LEFT_NODE] != -1) { int[] leftNode = splitTreeNodes.get(splitTree[LEFT_NODE]); int[] rightNode = splitTreeNodes.get(splitTree[RIGHT_NODE]); addPairs(leftNode, rightNode); computeWspd(leftNode); computeWspd(rightNode); } } private static double shortestDistance = Double.POSITIVE_INFINITY; private static void addPairs(int[] splitNode1, int[] splitNode2) { int[] box1 = boundingBoxes.get(splitNode1[BOUNDING_BOX]); int[] box2 = boundingBoxes.get(splitNode2[BOUNDING_BOX]); if (areWellSeparated(box1, box2)) { ArrayList pointXLeft = coordinateLists.get(splitNode1[X_COORDS]); ArrayList pointYLeft = coordinateLists.get(splitNode1[Y_COORDS]); ArrayList pointXRight = coordinateLists.get(splitNode2[X_COORDS]); ArrayList pointYRight = coordinateLists.get(splitNode2[Y_COORDS]); printPoints(pointXLeft, pointYLeft, pointXRight, pointYRight); if (pointXLeft.size() == 1 && pointXRight.size() == 1) { double newDist = distance(pointXLeft.get(0), pointYLeft.get(0), pointXRight.get(0), pointYRight.get(0)); if (newDist < shortestDistance) { shortestDistance = newDist; } } } else { if (longest(box1) >= longest(box2)) { addPairs(splitTreeNodes.get(splitNode1[LEFT_NODE]), splitNode2); addPairs(splitTreeNodes.get(splitNode1[RIGHT_NODE]), splitNode2); } else { addPairs(splitNode1, splitTreeNodes.get(splitNode2[LEFT_NODE])); addPairs(splitNode1, splitTreeNodes.get(splitNode2[RIGHT_NODE])); } } } private static void printPoints(ArrayList pointXLeft, ArrayList pointYLeft, ArrayList pointXRight, ArrayList pointYRight) { for(int i = 0; i < pointXLeft.size(); i++) { System.out.print(pointXLeft.get(i)); System.out.print(","); System.out.print(pointYLeft.get(i)); System.out.print(" "); } System.out.print("-"); for(int i = 0; i < pointXRight.size(); i++) { System.out.print(" "); System.out.print(pointXRight.get(i)); System.out.print(","); System.out.print(pointYRight.get(i)); } System.out.println(); } }