백준 2261번

원본 : www.acmicpc.net/problem/2261

2261번: 가장 가까운 두 점

 

풀이

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

public class Main {

	public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
	public static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

	public static void main(String[] args) throws Exception {
		int n = Integer.parseInt(reader.readLine());
		
		Point arrPoint[] = new Point[n];
		for (int i = 0; i < n; i++) {
			String strPoint = reader.readLine();
			arrPoint[i] = new Point(Integer.parseInt(strPoint.split(" ")[0]), Integer.parseInt(strPoint.split(" ")[1]));
		}
		Arrays.sort(arrPoint, new Comparator<Point>() {
			@Override
			public int compare(Point p1, Point p2) {
				if (p1.getX() > p2.getX()) {
					return 1;
				} else if (p1.getX() == p2.getX()) {
					return 0;
				} else {
					return -1;
				}
			}
		});
		
		TreeSet<Point> setPoint = new TreeSet<>();
		setPoint.add(arrPoint[0]);
		setPoint.add(arrPoint[1]);
		long minDistancePow = getDistancePow(arrPoint[0], arrPoint[1]);
		int sweepIndex = 0;
		
		for (int i = 2; i < n; i++) {
			Point currentPoint = arrPoint[i];
			while (sweepIndex < i) {
				if ((currentPoint.getX() - arrPoint[sweepIndex].getX()) * (currentPoint.getX() - arrPoint[sweepIndex].getX()) > minDistancePow) {
					setPoint.remove(arrPoint[sweepIndex]);
					sweepIndex++;
				} else {
					break;
				}
			}
			
			Point lowBoundPoint = new Point(-100000, currentPoint.getY() - (int)Math.ceil(Math.sqrt(minDistancePow)));
			Point upperBoundPoint = new Point(100000, currentPoint.getY() + (int)Math.ceil(Math.sqrt(minDistancePow)));
			
			for (Point prePoint : setPoint.subSet(lowBoundPoint, upperBoundPoint)) {
				long distancePow = getDistancePow(prePoint, currentPoint);
				if (distancePow < minDistancePow) {
					minDistancePow = distancePow;
				}
			}
			
			setPoint.add(currentPoint);
		}
		
		writer.write(minDistancePow + "");
		writer.flush();
	}

	public static class Point implements Comparable<Point> {
		private int x;
		private int y;
		
		public Point() {}
		
		public Point(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}

		public int getX() {
			return x;
		}

		public void setX(int x) {
			this.x = x;
		}

		public int getY() {
			return y;
		}

		public void setY(int y) {
			this.y = y;
		}

		@Override
		public int compareTo(Point o) {
			if (y == o.getY()) {
				return x - o.getX();
			} else {
				return y - o.getY();
			}
		}
	}
	
	public static long getDistancePow(Point p1, Point p2) {
		long x = p2.getX() - p1.getX();
		long y = p2.getY() - p1.getY();
		return x * x + y * y;
	}

}