Cod sursa(job #1551058)

Utilizator backtrackIconaru Marian Catalin backtrack Data 15 decembrie 2015 05:06:46
Problema Cele mai apropiate puncte din plan Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 3.03 kb
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

class Pair {
	private int x;
	private int y;

	public Pair(int x, int y) {
		this.x = x;
		this.y = y;
	}

	public int getFirst() {
		return this.x;
	}

	public int getSecond() {
		return this.y;
	}

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

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

}

class Divide {

	public double calculateDistance(Pair x, Pair y) {
		return Math.sqrt((x.getFirst() - y.getFirst()) * (x.getFirst() - y.getFirst())
				+ (x.getSecond() - y.getSecond()) * (x.getSecond() - y.getSecond()));
	}

	public Pair[] Merge(int a, int b, Pair[] X) {
		int mid = (b + a) / 2;
		int i = a;
		int j = mid + 1;
		Pair[] Y = new Pair[b - a + 1];
		int k = 0;
		while (i <= mid && j <= b)
			if (X[i].getFirst() < X[j].getFirst())
				Y[k++] = X[i++];
			else if (X[i].getFirst() >= X[j].getFirst())
				Y[k++] = X[j++];
		while (i <= mid)
			Y[k++] = X[i++];
		while (j <= b)
			Y[k++] = X[j++];
		return Y;
	}

	public double Merge(int a, int b, Pair[] X, Pair[] Y) {
		if (b - a < 1)
			return Double.MAX_VALUE;
		if (b - a == 1) {
			if (Y[a].getFirst() > Y[a + 1].getFirst()) {
				Pair aux = new Pair(Y[a].getFirst(), Y[a].getSecond());
				Y[a] = Y[a + 1];
				Y[a + 1] = aux;
			}
			return calculateDistance(X[a], X[a + 1]);
		}
		int med = (a + b) / 2;
		
		double first = Merge(a, med, X, Y);
		double second = Merge(med + 1, b, X, Y);
		double best = Math.min(first, second);
		Pair[] A = new Pair[b - a + 1];
		A = Merge(a, b, Y);
		for (int i = 0; i < A.length; i++)
			Y[a + i] = A[i];
		int k = 0;
		for (int i = a; i <= b; i++)
			if (Math.abs(Y[i].getSecond() - X[(a+b)/2].getFirst()) <= best)
				A[k++] = Y[i];
		for (int i = 0; i < k - 1; ++i)
			for (int j = i + 1; j < k && j-i<8; ++j)
				best = Math.min(best, calculateDistance(A[i], A[j]));
		return best;
	}

	public void sort(Pair[] X) {
		Arrays.sort(X, new Comparator<Pair>() {
			@Override
			public int compare(Pair x, Pair y) {
				return x.getFirst() - y.getFirst();
			}
		});
	}
}

class Main {
	public static void main(String[] args) {
		Scanner scan;
		try {
			scan = new Scanner(new FileInputStream("cmap.in"));
		} catch (FileNotFoundException e) {
			e.printStackTrace();
			scan = null;
		}
		int n = scan.nextInt();

		Pair[] x = new Pair[n];
		for (int i = 0; i < n; i++)
			x[i] = new Pair(scan.nextInt(), scan.nextInt());
		Divide ok = new Divide();
		ok.sort(x);
		Pair[] y = new Pair[n];
		for (int i = 0; i < n; i++)
			y[i] = new Pair(x[i].getSecond(), x[i].getFirst());
		scan.close();
		PrintWriter print;
		try {
			print = new PrintWriter(new FileOutputStream("cmap.out"));
		} catch (FileNotFoundException e) {
			e.printStackTrace();
			print = null;
		}

		double a = (ok.Merge(0, n-1, x, y)); //* Math.pow(10, 6));
//		int precision = (int) Math.ceil(a);
	//	a = (double) precision / Math.pow(10, 6);
		print.println(a);
		scan.close();
		print.close();
	}
}