백준 2261 자바 - 가장 가까운 두 점

https://www.acmicpc.net/problem/2261

2261번: 가장 가까운 두 점

문제

2차원 평면상에 n개의 점이 주어졌을 때, 이 점들 중 가장 가까운 두 점을 구하는 프로그램을 작성하시오.

코드

import java.io.*;
import java.util.*;

public class Main {

    private static Element[] elements;

    private static Comparator<Element> yCompare = new Comparator<>() {
        @Override
        public int compare(Element o1, Element o2) {
            return o1.y - o2.y;
        }
    };

    private static Comparator<Element> xCompare = new Comparator<>() {
        @Override
        public int compare(Element o1, Element o2) {
            return o1.x - o2.x;
        }
    };

    public static void main(String[] args) throws IOException {
        BufferedWriter bw  = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        elements = new Element[n];

        StringTokenizer st;

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            elements[i] = new Element(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }
        Arrays.sort(elements, xCompare);

        bw.write(String.valueOf(closest(0, n - 1)));
        bw.flush();
    }

    private static int closest(int start, int end) {
        if (end - start + 1 < 4) {
            return brute(start, end);
        }
        int mid = (start + end) / 2;

        int left = closest(start, mid);
        int right = closest(mid + 1, end);

        int minDist = Math.min(left, right);

        int band = middleBand(start, mid, end, minDist);
        return Math.min(minDist, band);
    }

    private static int brute(int start, int end) {

        int minDist = Integer.MAX_VALUE;

        for (int i = start; i < end; i++) {
            Element x0 = elements[i];
            for (int j = i + 1; j <= end; j++) {
                minDist = Math.min(minDist, dist(x0, elements[j]));
            }
        }
        return minDist;
    }

    private static int middleBand(int start, int mid, int end, int minDist) {
        int xDist;
        ArrayList<Element> list = new ArrayList<>();

        int midX = elements[mid].x;
        for (int i = start; i <= end; i++) {
            xDist = elements[i].x - midX;
            if (xDist * xDist < minDist) {
                list.add(elements[i]);
            }
        }

        Collections.sort(list, yCompare);

        int yDist;
        for (int i = 0; i < list.size() - 1; i++) {
            for (int j = i + 1; j < list.size(); j++) {
                yDist = list.get(i).y - list.get(j).y;
                if (yDist * yDist < minDist) {
                    minDist = Math.min(dist(list.get(i), list.get(j)), minDist);
                }
                else {
                    break;
                }
            }
        }
        return minDist;
    }

    private static int dist(Element e1, Element e2) {
        return (e1.x - e2.x) * (e1.x - e2.x) + (e1.y - e2.y) * (e1.y - e2.y);
    }

    private static class Element {
        int x;
        int y;

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

풀이

 분할 정복으로 풀었다. Element라는 클래스로 x, y 축 값을 다룬다. dist라는 함수를 활용해 거리를 구한다. 분할정복으로 중간 지점에서 왼쪽, 오른쪽을 나누어 들어가며 탐색한다. 각 점들을 하나의 축으로 정렬해주는 익명 클래스 두 개를 활용해 정렬을 해야한다. 왼쪽이나 오른쪽으로 나눈 부분에서 최솟값을 알아야 하고, 그 다음 분할된 위치 mid를기준으로 원소들을 추출해 후보군을 만든다. 후보 원소들에 대해 y축 정렬을 수행한다.  dist가 최소인 값을 계속 갱신해준다.