[KOITP] 가장 가까운 두 점

출    처 : http://koitp.org/problem/SDS_PRO_7_7/read/

시간 제한	메모리 제한	제출 횟수	정답 횟수 (비율)	정답자 수
4.0 초	512 MB	726	87 (12%)	73

문제

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

제한시간 : 2초

입력

첫째 줄에 자연수 n(2≤n≤500,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다.

출력

첫째 줄에 가장 가까운 두 점의 거리의 제곱을 출력한다.

힌트

입력 예제

4
0 0
10 10
0 10
10 0

출력 예제

100

< Comment >

 사실 너무 아슬아슬하게 통과해서, 이걸 맞췄다고 봐야할지도 애매한 것 같습니다.

 그렇지만 우선 테스트 케이스 자체는 통과하였기에 작성합니다. 시간 제한 때문에 상당한 시간동안 고민했었는데, 처음에 시간제한인 4초를 넘어 5초 가까이 나왔던 것은, 제곱한 값을 거리로 보고 진행해야 했었는데, 현재 거리값만 제곱해 두고, 새로 구하는 최소값들은 제곱을 해 주지 않아, 훨씬 많은 대상이 뽑혔던 것으로 보입니다.

 기본적으로 여기서 시간이 많이 소비되었고, 다음으로는 ArrayList 를 사용했기 때문에도 약간 시간이 늘었었습니다. Arrays.sort()에 범위 지정하는 기능이 없다고 생각하여, ArrayList를 사용하였는데, 이를 생성하고 값을 입력하는 과정이 일반적인 Array 보다 길었습니다.

 문제 자체는 개인적으로 처음에 이해하기도 힘들었습니다. Recursive 로 작성된 것들이 늘 그렇듯이, 이미 답은 구해져있다고 가정하고 푸는 것인데, 이게 익숙하지 않아서 그랬던 것 같습니다. 기본 사상은 가운데에 양쪽의 점의 개수가 동일하게 되도록 나눈 후, 좌측에서 가장 짧은 거리에 있는 점 사이의 거리와, 우측에서 가장 짧은 거리에 있는 점 사이의 거리, 마지막으로 그 둘 중 작은 거리보다, 작은 거리를 가지는 좌 우측에 걸친 점의 최소 거리. 이 셋 중 가장 작은 것을 구하는 것이었습니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class ClosePoints {
	
	public static int N = 0;
	public static long INF = Long.MAX_VALUE;
	
	public static Point points[] = null;
	
	public static class Point {
		
		long x = 0;
		long y = 0;
		
		public Point(long x, long y) {
			this.x = x;
			this.y = y;
		}
		
		public long getDistPow(Point p2) {
			return (long)(Math.pow(this.x - p2.x, 2) + Math.pow(this.y - p2.y, 2)); 
		}
	}
	
	public static class yComparator implements Comparator<Point>{

		@Override
		public int compare(Point o1, Point o2) {
			if (o1 == null && o2 == null) 	return 0;
            if (o1 == null) 				return 1;
            if (o2 == null)					return -1;
            
			if (o1.y > o2.y)	return 1;
			if (o1.y < o2.y)	return -1;
			return 0;
		}
	}
	
	public static class xComparator implements Comparator<Point>{

		@Override
		public int compare(Point o1, Point o2) {
			
			if (o1.x > o2.x)	return 1;
			if (o1.x < o2.x)	return -1;
			return 0;
		}
	}

	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		N = Integer.parseInt(br.readLine());
		
		StringTokenizer st = null;
		long x = 0;
		long y = 0;
		points = new Point[N];
		for (int i = 0 ; i < N ; i++) {
			
			st = new StringTokenizer(br.readLine());
			x = Integer.parseInt(st.nextToken());
			y = Integer.parseInt(st.nextToken());
			points[i] = new Point(x, y);
		}
		
		Arrays.sort(points, new xComparator());
		
		// 0 ~ N-1
		long result = closeDist(0, N-1);
		
		bw.write("" + (result));
		bw.flush();
		bw.close();
	}
	
	public static long closeDist(int s, int e) {
		
		if (s == e) {
			return INF;
		}
		
		int m = (s + e) / 2;
		
		long left = closeDist(s, m);			// 좌측에서의 점간 최소거리
		long right = closeDist(m + 1, e);		// 우측에서의 점간 최소거리
		
		long d = Math.min(left, right);			// 좌 우 중 더 작은 최소거리 d
		
		Point midP = points[m];
		Point bandPs[] = new Point[e - s + 1];
		
		int size = 0;	// 중간 Band에 존자하는 점들의 갯수
		for (int i = s ; i <= e ; i++) {	// 만약 좌측과 우측의 최단거리보다 좁은 범위에 있는 점들이 있다면, 이를 별도 배열 bandPS에 저장

			if (Math.pow(points[i].x - midP.x, 2) <= d) {
				bandPs[size++] = points[i];
			}
		}
		
		Arrays.sort(bandPs, 0, size, new yComparator());
		
		long minDist = d;
		for (int i = 0 ; i < size ; i++) {
			
			for (int j = i + 1 ; j < size ; j++) {
				
				if (Math.pow(bandPs[i].y - bandPs[j].y, 2) < minDist) {		// 정렬된 상태이기 때문에, 범위내 y축 상으로 d보다 가까운 점이 있으면 거리를 계산하여 갱신
					 minDist = Math.min(minDist, bandPs[i].getDistPow(bandPs[j]));
				} else {	// 정렬된 상태에서 더욱 커지면 이후는 유망하지 않으므로 break
					break;
				}
			}
		}
		
		return minDist;
	}
}