Pagini recente » Cod sursa (job #68079) | Cod sursa (job #2124920) | Cod sursa (job #2084476) | Cod sursa (job #42764) | Cod sursa (job #1551069)
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();
}
}