Pagini recente » Cod sursa (job #3283364) | Cod sursa (job #1155092) | Cod sursa (job #2069764) | Cod sursa (job #2149157) | Cod sursa (job #1551057)
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();
}
}