BOJ. Closest two Point (2261)

import java.util.*;
import java.util.stream.Stream;
import java.io.*;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int[] line;
    int n = Integer.parseInt(br.readLine());
    Point[] p = new Point[n];
    for(int i = 0; i < n; i++) {
      line = getLine(br);
      p[i] = new Point(line[0], line[1]);
    }
    Arrays.sort(p, (l,r) -> l.x - r.x);
    System.out.print(binSearch(p, 0, n - 1, Integer.MAX_VALUE));
  }

  private static int binSearch(Point[] p, int start, int end, int min) {
    // (2 -> 3Points) Under 3 Points(3 points -> 1 , 2 -> 1 is not searched)
    if(end - start <= 2) {
      for(int i = start; i <= end; i++) {
        for(int j = i + 1; j <= end; j++) {
          int dis = dis(p[i], p[j]);
          if(dis < min) min = dis;
        }
      }
      return min;
    }
    int mid = (start + end) / 2;
    int tempMin = Math.min(binSearch(p, start, mid, min), binSearch(p, mid + 1, end, min));
    min = Math.min(min, tempMin);
    return Math.min(midSearch(p, start, end, tempMin), min);
  }

  private static int midSearch(Point[] p, int start, int end, int lrMin) {
    ArrayList<Point> al = new ArrayList<>();
    int min = Integer.MAX_VALUE, mid = (start + end) / 2;
    for(int i = start; i <= end; i++) {
      int xDiff = p[i].x - p[mid].x;
      if(xDiff * xDiff < lrMin) al.add(p[i]);
    }
    al.sort((l, r) -> l.y - r.y);

    for(int i = 0; i < al.size(); i++) {
      Point lowP = al.get(i);
      for(int j = i + 1; j < al.size(); j++) {
        int yDiff = al.get(j).y - lowP.y;
        if(yDiff * yDiff < lrMin) {
          int dis = dis(lowP, al.get(j));
          if(dis < min) min = dis;
        } else break;
      }
    }
    return min;
  }

  private static int dis(Point p1, Point p2) {
    return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
  }

  public static class Point {
    int x;
    int y;
    Point(int x, int y) { this.x = x; this.y = y; }
  }

  private static int[] getLine (BufferedReader br) throws IOException {
    return Stream.of(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
  }
}