UVa 10245 - The Closest Pair Problem

// UVa 10245 - The Closest Pair Problem

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        for (int n = scanner.nextInt(); n != 0; n = scanner.nextInt()) {
            List<Point> points = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                points.add(new Point(scanner.nextDouble(), scanner.nextDouble()));
            }
            points.sort(Comparator.comparing(p -> p.x));

            ClosestPointsFinder cpf = new ClosestPointsFinder(points);
            double closestPointsDistance = cpf.getClosestPointsDistance();
            if (closestPointsDistance < 10000) {
                System.out.printf("%.4f\n", closestPointsDistance);
            } else {
                System.out.println("INFINITY");
            }
        }
    }

    private static class Point {
        final double x, y;

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

        double distance(Point other) {
            double x2 = Math.pow(this.x - other.x, 2);
            double y2 = Math.pow(this.y - other.y, 2);
            return Math.sqrt(x2 + y2);
        }
    }

    private static class ClosestPointsFinder {
        private static double INFINITY = 10000;
        private final List<Point> points;

        ClosestPointsFinder(List<Point> points) {
            this.points = points;
        }

        double getClosestPointsDistance() {
            return getClosestPointsDistance(0, points.size(), INFINITY);
        }

        private double getClosestPointsDistance(int start, int end, double distSoFar) {

            if (start + 2 == end) {
                return points.get(start).distance(points.get(start + 1));
            } else if (start + 1 >= end) {
                return INFINITY;
            }

            int mid = (start + end) / 2;

            double subDist = getClosestPointsDistance(start, mid, distSoFar);
            if (subDist < distSoFar)
                distSoFar = subDist;

            subDist = getClosestPointsDistance(mid, end, distSoFar);
            if (subDist < distSoFar)
                distSoFar = subDist;

            List<Point> strip = new ArrayList<>();
            for (int i = mid - 1; i >= start; i--) {
                if (points.get(i).x + distSoFar >= points.get(mid - 1).x) {
                    strip.add(points.get(i));
                } else {
                    break;
                }
            }
            for (int i = mid; i < end; i++) {
                if (points.get(mid - 1).x + distSoFar >= points.get(i).x) {
                    strip.add(points.get(i));
                } else {
                    break;
                }
            }
            strip.sort(Comparator.comparing(p -> p.y));

            for (int i = 0; i < strip.size(); i++) {
                for (int j = i + 1; j < strip.size() && j < i + 8; j++) {
                    subDist = strip.get(i).distance(strip.get(j));
                    if (subDist < distSoFar)
                        distSoFar = subDist;
                }
            }

            return distSoFar;
        }
    }
}