[BOJ] 백준 5620 가장 가까운 두 점의 거리

출처:  https://www.acmicpc.net/problem/5620

 Input 

3

5 5

0 0

-3 -4

 

 Output 

25

N의 범위가 충분히 크기 때문에 완전 탐색이나 분할 정복 기법으로는 TLE 발생.

Line Sweep 알고리즘을 사용합니다.

 

※ y 좌표 기준에 따른 비교대상 선정을 TreeSet을 이용해서 시간 효율 Up

   set에는 항상 입력받은 배열의 한 구간이 들어가있게 됩니다. 

   그 구간의 끝점은 항상 i-1이 됩니다. 

   시작이 어디인지를 변수 start에 저장하면 됩니다.

 

x좌표에는 -100,000을 넣는 이유는 같은 y좌표를 가지는 점이 여러 개일 때, 

가능한 x좌표의 값 중 가장 작은 값(-10,000)보다 작기 때문입니다. (upper_bound도 마찬가지 입니다.)

---

import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new   InputStreamReader(System.in));
        StringTokenizer st = null;
         
        int N = Integer.parseInt(br.readLine());
        Point[] points = new Point[N]; 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            points[i] = new Point(x, y);
        }
         
        // 좌표를 x값 기준으로 오름차순 정렬
        Arrays.sort(points, (a, b) -> (a.x - b.x));
         
        // TreeSet을 이용하여 1차적으로 y값 기준으로 오름차순
        // y값이 동일하면 x값 기준 오름차순이 정렬
        TreeSet<Point> set = new TreeSet<>((a, b) -> ((a.y == b.y) ? a.x - b.x : a.y - b.y));
         
        set.add(points[0]);
        set.add(points[1]);
        // 첫번째 좌표와 두번째 좌표간 거리의 제곱을 기준.
        long answer = distance(points[0], points[1]);
         
        int start = 0;
        // 3번째~N번째 좌표
        for (int idx = 2; idx < N; idx++) {
            Point cur = points[idx];
            //set에 있는 점들의 유효성 검사
            while (start < idx) {
                Point point = points[start];
                long x = cur.x - point.x;
                // answer 변수에 거리의 제곱으로 저장되어 있으므로  x*x로 비교
                // 정확한 계산처리를 위해 제곱으로 계산
                if (x * x > answer) {
                    set.remove(point);
                    start++;
                } else {
                    break;
                }
            }
             
            int d = (int) Math.sqrt((double) answer) + 1;
            //y값의 범위를 구해줌
            Point from = new Point(-100000, cur.y - d); // 아래
            Point to = new Point(100000, cur.y + d); // 위
            for (Point point : set.subSet(from, to)) {
                long distance = distance(cur, point);
                answer = Math.min(answer, distance);
            }
            set.add(cur);
        }
         
        System.out.println(answer);
    }
     
    private static long distance(Point A, Point B) {
        return (long)((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
    }
}
 
class Point{
    int x, y;
    public Point(int x, int y){
        this.x = x;
        this.y = y;
    }
}