public static double closestPair(List<Point> points) {
    List<Point> ys = new ArrayList<>(points);
    Util.sortByY(ys);
    Util.sortByX(points);
    return closest(points, ys);
  }

  public static double closest(List<Point> points, List<Point> pointsY){
    int size = points.size();
    if (size <= 3){
      return Util.bruteForce(points);
    }

    int mid = size/2;
    Point midPoint = points.get(mid);

    List<Point> left = points.subList(0, mid);
    List<Point> right = points.subList(mid, points.size());

    List<Point> smthleft = new ArrayList<>();
    List<Point> smthright = new ArrayList<>();
    for (Point point : pointsY){
      if (point.x < midPoint.x){
        smthleft.add(point);
      }
      else {
        smthright.add(point);
      }
    }

    double dl = closest(left, smthleft);
    double dr = closest(right, smthright);

    double d = (dl > dr) ? dr : dl;

    List<Point> midStrip = new ArrayList<>();

    double midX = left.get(left.size() - 1).x;

    for (Point p : pointsY){
      if (Math.abs(p.x - midX) <= d){
        midStrip.add(p);
      }
    }

    for (int i = 0; i < midStrip.size() - 1; i++) {
      Point point1 = midStrip.get(i);
      // midStrip.size() && (midStrip.get(j).y - midStrip.get(i).y < d)
      for (int j = i + 1; j < midStrip.size() && (midStrip.get(j).y - midStrip.get(i).y < d); j++) {
        Point point2 = midStrip.get(j);
        double distance = Util.distance(point1, point2);
        if (distance < d) {
          d = distance;
        }
      }
    }

    return d;
  }