Cod sursa(job #1551069)

Utilizator backtrackIconaru Marian Catalin backtrack Data 15 decembrie 2015 06:12:43
Problema Cele mai apropiate puncte din plan Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 3.07 kb

import java.io.*;
import java.util.*;

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 long calculateDistance(Pair x, Pair y) {
		return (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 long Merge(int a, int b, Pair[] X, Pair[] Y) {
		if (b - a + 1 <= 3) {
			long dist = Long.MAX_VALUE;
			for (int i = a; i < b; i++)
				for (int j = i + 1; j < b; j++)
					if (calculateDistance(X[i], X[j]) < dist)
						dist = calculateDistance(X[i], X[j]);
			return dist;
		}
		int med = (a + b) / 2;

		long first = Merge(a, med, X, Y);
		long second = Merge(med + 1, b, X, Y);
		long best = Math.min(first, second);
		Pair[] A = new Pair[b - a + 1];
		// A = Merge(a, b, Y);
		int i = a;
		int j = (b + a) / 2 + 1;
		int mid = (b + a) / 2;
		int k = 0;
		while (i <= mid && j <= b)
			if (Y[i].getFirst() < Y[j].getFirst())
				A[k++] = Y[i++];
			else
				A[k++] = Y[j++];
		while (i <= mid)
			A[k++] = Y[i++];
		while (j <= b)
			A[k++] = Y[j++];
		for (i = a; i <= b; i++)
			Y[i] = A[i - a];
		k = 0;
		Pair[] Final = new Pair[A.length];
		for (i = a; i <= b; i++)
			if (Math.abs(Y[i].getSecond() - X[(a + b) / 2].getFirst()) < best)
				Final[k++] = Y[i];
		for (i = 0; i < k - 1; ++i)
			for (j = i + 1; j < k && j - i < 8; ++j)
				best = Math.min(best, calculateDistance(Final[i], Final[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 = null;
		try {
			scan = new Scanner(new FileInputStream("cmap.in"));
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
		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());

		PrintWriter p;
		try {
			p = new PrintWriter((OutputStream) new FileOutputStream("cmap.out"));
		} catch (FileNotFoundException e) {
			e.printStackTrace();
			p = null;
		}
		long a = (ok.Merge(0, n - 1, x, y));
		double da=Math.sqrt(a)*Math.pow(10, 6);
		a = (long) Math.ceil(da);
		 da = (double) a / Math.pow(10, 6);
		 p.print(da);
		scan.close();
		p.close();
	}
}