#백준_2261 가장 가까운 두 점

#유형 : 분할 정복 

# 간단한 알고리즘으로는 시간 초과를 벗어날 수 없음.. 풀었던 방법은

1) X좌표를 기준으로 정렬을 하여 middle index를 기준으로 왼쪽,오른쪽에서 가장 가까운 거리, middle 을 가로지르는 두 점간의 가장 가까운거리 3가지를 구해야 한다.

2) 왼쪽에서 가장 가까운 두점 사이의 거리, 오른쪽에서 가장 가까운 두점사이의 거리를 구하여 Min_value를 정해놓고, 이 값을 이용하여 middle index를 가로지르는 두 점간의 가장 가까운 거리를 구하여 min_value보다 작은 값들을 리스트에 넣는다.

3) 리스트를 Y좌표를 기준으로 정렬을 하여 y좌표들 간의 거리의 제곱이 stand보다 작은 값들만 거리를 구해서 비교하며 최솟값을 찾으면 된다.

 

 

package bj;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;

public class p2261 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		ArrayList arrList = new ArrayList<>();
		StringTokenizer st;
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y= Integer.parseInt(st.nextToken());
			arrList.add(new Point(x,y));
		}
		
		Collections.sort(arrList);
		System.out.println(solve(arrList, 0, N-1));
	}
	
	
	static int solve(ArrayList p, int x, int y) {
		int limit = y-x+1;
		
		if(limit<=3)
			return search(p, x, y);
		
		int middle = (x+y)/2;
		int left = solve(p, x, middle);
		int right = solve(p, middle+1, y);
		int stand = Math.min(left, right);
		
		ArrayList tmp = new ArrayList<>();
		for(int i=x; i<=y; i++) {
			int dist = p.get(i).x - p.get(middle).x;
			if(dist*dist < stand)
				tmp.add(p.get(i));
			
		}
		
		Collections.sort(tmp, new point_compartor());
		
		int size = tmp.size();
		for(int i=0; i<size-1; i++) {
			for(int j=i+1; j<size; j++) {
				int val = tmp.get(i).y - tmp.get(j).y;
				if(val*val < stand) {
					int d = getDistance(tmp.get(i), tmp.get(j));
					if(d < stand)
						stand = d;
				}else
					break;
			}
		}
		
		return stand;
	}
	public static int getDistance(Point p1, Point p2) {
		int result = (int) (Math.pow(p1.x-p2.x, 2) + Math.pow(p1.y - p2.y, 2));
		return result;
	}
	public static int search(ArrayList p, int x, int y) {
		int rs = -1;
		for(int i=x; i<=y-1; i++) {
			for(int j=i+1; j<=y; j++) {
				int val = getDistance(p.get(i), p.get(j));
				if(rs==-1 || rs>val)
					rs=val;
			}
		}
		return rs;
	}
	public static class Point implements Comparable{
		int x;
		int y;
		public Point(int x,int y) {
			this.x=x;
			this.y=y;
		}
		@Override
		public int compareTo(Point o) {
			int val = this.x - o.x;
			if(val == 0) {
				return this.y-o.y;
			}else
				return val;
		}
	}
	
	public static class point_compartor implements Comparator{

		@Override
		public int compare(Point o1, Point o2) {
			// TODO Auto-generated method stub
			return o1.y-o2.y;
		}
	}
}