[SWEA] 4042 Closest

출처: [SWEA] SW 문제해결 심화 - 계산기하학

 Input 

1

4

0 0

10 10

0 10

10 0

 

 Output 

#1 100

 

※ [BOJ] 5620 가장 가까운 두 점의 거리 풀이 참조

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

 

---

- x, y 좌표 범위가 크므로 long으로 표현

- 효율적인 메모리를 위해 Comparable보다 Comparator이용!

import java.io.*;
import java.util.*;
 
public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
         
        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
             
            int N = Integer.parseInt(br.readLine());
            Point[] points = new Point[N];
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                long x = Long.parseLong(st.nextToken());
                long y = Long.parseLong(st.nextToken());
                points[i] = new Point(x, y);
            }
             
            // 좌표를 x값 기준으로 오름차순 정렬
            Arrays.sort(points, new xComparator());
 
            // (1차) y좌표 기준으로 오름차순 정렬
            // (2차) x좌표 기준으로 오름차순 정렬
            TreeSet <Point> set = new TreeSet <Point> (new Comp());
            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(-100001 , cur.y - d);
                Point to = new Point(100001, 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("#" + tc + " " + answer);
        }
    }
     
    private static long distance(Point A, Point B) {
        return (A.x - B.x)*(A.x - B.x) + (A.y - B.y)*(A.y - B.y);
    }
}
 
class xComparator implements Comparator<Point> {
    @Override
    public int compare(Point p1, Point p2) {
        if(p1.x - p2.x < 0) return -1;
        else if(p1.x - p2.x > 0) return 1;
        else return 0;
    }
}
  
class Comp implements Comparator<Point> {
    // y값이 동일하면 x값 기준 오름차순이 정렬
    @Override
    public int compare(Point p1, Point p2) {
        if(p1.y - p2.y < 0) return -1;
        else if(p1.y - p2.y > 0) return 1;
        else {
            if(p1.x - p2.x < 0) return -1;
            else if(p1.x - p2.x > 0) return 1;
            else return 0;
        }
    }
}
 
class Point {
    long x, y;
 
    public Point(long x, long y) {
        this.x = x;
        this.y = y;
    }
}