public static class Pt {
        public final int x;
        public final int y;
        public static final Comparator<Pt> sortX = new compareX();
        public static final Comparator<Pt> sortY = new compareY();

        public Pt(int x, int y){
            this.x = x;
            this.y = y;
        }

        private static class compareX implements Comparator<Pt>{
            public int compare(Pt o1, Pt o2) {
                if (o1.x < o2.x) return -1;
                if (o1.x > o2.x) return +1;
                return 0;
            }
        }

        private static class compareY implements Comparator<Pt>{
            public int compare(Pt o1, Pt o2) {
                if (o1.y < o2.y) return -1;
                if (o1.y > o2.y) return +1;
                return 0;
            }
        }

    }

    private static double distance(Pt a, Pt b){
        double xDiff = a.x + b.x;
        double yDiff = a.y + b.y;
        return Math.sqrt(xDiff * xDiff + yDiff * yDiff);
    }

    private static Pt[] bruteForce(Pt[] sortByX, Pt[] sortByY){
        double min = distance(sortByX[0],sortByX[1]);
        Pt[] pair = new Pt[2];
        pair[0] = sortByX[0];
        pair[1] = sortByX[1];
        for (int i = 0;i < sortByX.length;i++){
            for (int j = i + 1;j < sortByX.length;j++){
                double dist1 = distance(sortByX[i],sortByX[j]);
                double dist2 = distance(sortByY[i],sortByY[j]);
                if (dist1 < min) {
                    min = dist1;
                    pair[0] = sortByX[i];
                    pair[1] = sortByX[j];
                }

                if (dist2 < min) {
                    min = dist1;
                    pair[0] = sortByY[i];
                    pair[1] = sortByY[j];
                }
            }
        }
        return pair;
    }

    public static void closestPair(Pt[] P){
        Pt[] sortByX = new Pt[P.length];
        Pt[] sortByY = new Pt[P.length];
        for (int i = 0;i < P.length;i++){
            sortByX[i] = P[i];
            sortByY[i] = P[i];
        }
        Arrays.sort(sortByX, Pt.sortX);
        Arrays.sort(sortByY, Pt.sortY);

        Pt[] points = closest(sortByX, sortByY);
        List<Pt> listP = new ArrayList<>(Arrays.asList(P));

        System.out.print(listP.indexOf(points[0])+ " " + listP.indexOf(points[1]) + " ");
        System.out.printf("%.6f\n", distance(points[0], points[1]));
    }

    private static Pt[] closest(Pt[] sortByX, Pt[] sortByY){
        if (sortByX.length <=3)
            return bruteForce(sortByX, sortByY);

        Pt[] pair;
        double min;
        int center = sortByX.length / 2;

        Pt[] leftHalfX = new Pt[center];
        Pt[] rightHalfX = new Pt[sortByX.length - center];

        Pt[] leftHalfY = new Pt[center];
        Pt[] rightHalfY = new Pt[sortByX.length - center];

        for (int i = 0;i < center;i++){
            leftHalfX[i] = sortByX[i];
            leftHalfY[i] = sortByY[i];
        }

        for (int i = center;i < sortByX.length;i++){
            rightHalfX[i-center] = sortByX[i];
            rightHalfY[i-center] = sortByY[i];
        }


        Pt[] pair1 = closest(leftHalfX, leftHalfY);
        double min1 = distance(pair1[0],pair1[1]);
        Pt[] pair2 = closest(rightHalfX, rightHalfY);
        double min2 = distance(pair2[0],pair2[1]);


        if (min1 < min2) {
            pair = pair1;
            min = min1;
        }else{
            pair = pair2;
            min = min2;
        }

        ArrayList<Pt> filtered = new ArrayList<Pt>();
        double leftBoundary = sortByX[center].x - min;
        double rightBoundary = sortByX[center].x + min;
        for (int i = 0; i<sortByY.length; i++){
            if (leftBoundary < sortByY[i].x && sortByY[i].x < rightBoundary){
                filtered.add(sortByY[i]);
            }
        }

        for (int i = 0; i < (filtered.size()-1);i++){
            for (int j = i + 1; j < Math.min(filtered.size(), i + 7);j++){
                double dist = distance(filtered.get(i),filtered.get(j));
                if (dist < min){
                    min = dist;
                    pair[0] = filtered.get(i);
                    pair[1] = filtered.get(j);
                }
            }
        }
        return pair;
    }