Cod sursa(job #1847508)

Utilizator diana97Diana Ghinea diana97 Data 14 ianuarie 2017 18:03:38
Problema Cele mai apropiate puncte din plan Scor 40
Compilator java Status done
Runda Arhiva educationala Marime 2.61 kb
import java.util.*;
import java.io.*;

class Point implements Comparable<Point>{
	double x, y;

	Point() {}

	Point(Scanner scanner) {
		x = scanner.nextDouble();
		y = scanner.nextDouble();
	}

	public static double distance(Point a, Point b) {
		double dx = a.x - b.x;
		double dy = a.y - b.y;
		return Math.sqrt(dx * dx + dy * dy);
	}

	public int compareTo(Point other) {
		if (x < other.x) return -1;
		if (x == other.x) return 0;
		return 1;
	}
}

class Main {
	private static int n;
	private static Point[] points;
	private static Point[] aux;
	private static Point[] middlePoints;

	public static void main(String[] args) {

		try {
			File inputFile = new File("cmap.in");
			File outputFile = new File("cmap.out");

			FileInputStream inputStream = new FileInputStream(inputFile);
			Scanner scanner = new Scanner(inputStream);
			readData(scanner);
			scanner.close();
			inputStream.close();

			FileOutputStream outputStream = new FileOutputStream(outputFile);
			PrintWriter writer = new PrintWriter(outputStream);
			Arrays.sort(points);
			writer.print(getClosestPair(0, n - 1));
			writer.print('\n');
			writer.close();
			outputStream.close();

		} catch(IOException e) {};
	}

	private static void readData(Scanner scanner) {
		n = scanner.nextInt();
		points = new Point[n];
		aux = new Point[n];
		middlePoints = new Point[n];
		for (int i = 0; i < n; i++)
			points[i] = new Point(scanner);
	}

	private static void interclaseaza(int start, int end) {
		int mid = (start + end) / 2;
		int i = start;
		int j = mid + 1;
		int k = 0;

		while (i <= mid && j <= end) {
			if (points[i].y < points[j].y)
				aux[k++] = points[i++];
			else aux[k++] = points[j++];
		}

		for (; i <= mid; i++) aux[k++] = points[i];
		for (; j <= end; j++) aux[k++] = points[j];

		for (int l = 0; l < k; l++)
			points[start + l] = aux[l];
	}

	private static double getClosestPair(int start, int end) {
		if (start + 1 == end) {
			if (points[end].y < points[start].y) {
				Point aux = points[end];
				points[end] = points[start];
				points[start] = aux;
			}
			return Point.distance(points[start], points[end]);
		}

		if (start >= end) return 0x3fffffff;


		int mid = (start + end) / 2;
		double middleX = points[mid].x;
		double sol = Math.min(
				getClosestPair(start, mid),
				getClosestPair(mid + 1, end)
			);

		interclaseaza(start, end);

		int k = 0;
		for (int i = start; i <= end; i++)
			if (Math.abs(points[i].x - middleX) <= sol)
				middlePoints[k++] = points[i];


		for (int i = 0; i < k; i++)
			for (int j = i + 1; j < Math.min(k, i + 8 + 1); j++)
				sol = Math.min(sol, Point.distance(middlePoints[i], middlePoints[j]));

		return sol;
	}
}