Cod sursa(job #2265731)

Utilizator kitkat007Graphy kitkat007 Data 21 octombrie 2018 16:54:06
Problema Cele mai apropiate puncte din plan Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 3.16 kb
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    private static final int UNDEFINED = -1;
    private static List<Point> points = new ArrayList<>();

    static class Point {
        long x, y;

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

        long distanceTo(Point that) {
            return (this.x - that.x) * (this.x - that.x) + (this.y - that.y) * (this.y - that.y);
        }
    }

    public static void main(String[] args) throws FileNotFoundException {
        Scanner sc = new Scanner(new FileReader("cmap.in"));
        PrintWriter pw = new PrintWriter("cmap.out");
        //     Scanner sc = new Scanner(System.in);
        //  int t = sc.nextInt();
        // while (t-- > 0) {
        int n = sc.nextInt();
        while (n-- > 0) {
            long x = sc.nextInt();
            long y = sc.nextInt();
            points.add(new Point(x, y));
        }
        points.sort((p0, p1) -> {
            int temp = Long.compare(p0.x, p1.x);
            if (temp == 0) {
                return Long.compare(p0.y, p1.y);
            }
            return temp;
        });
        double ans = Math.sqrt(getMinimumDistance(0, points.size() - 1));
        pw.println(Math.floor(ans * 100000) / 100000);
        //  }
    }

    private static long getMinimumDistance(int left, int right) {
        if (right - left + 1 <= 3) {
            long minDist = UNDEFINED;
            for (int i = left; i < right; ++i) {
                Point p0 = points.get(i);
                for (int j = i + 1; j <= right; ++j) {
                    Point p1 = points.get(j);
                    if (minDist == UNDEFINED) {
                        minDist = p0.distanceTo(p1);
                    } else {
                        minDist = Math.min(minDist, p0.distanceTo(p1));
                    }
                }
                return minDist;
            }
        }
        int mid = (left + right) >> 1;
        long minDist0 = getMinimumDistance(left, mid);
        long minDist1 = getMinimumDistance(mid + 1, right);
        long minDist = Long.min(minDist0, minDist1);
        Point splitPoint = points.get(mid);
        List<Point> nearestPoints = new ArrayList<>();
        for (int i = left; i <= right; ++i) {
            Point p = points.get(i);
            if (Math.abs(splitPoint.x - p.x) <= minDist) {
                nearestPoints.add(p);
            }
        }
        nearestPoints.sort((p0, p1) -> {
            int temp = Long.compare(p0.y, p1.y);
            if (temp == 0) {
                return Long.compare(p0.x, p1.x);
            }
            return temp;
        });
        for (int i = 0; i < nearestPoints.size() - 1; ++i) {
            Point p0 = nearestPoints.get(i);
            for (int j = i + 1; j < nearestPoints.size() && j - i <= 7; ++j) {
                Point p1 = nearestPoints.get(j);
                minDist = Math.min(minDist, p0.distanceTo(p1));
            }
        }
        return minDist;
    }
}