Pagini recente » Cod sursa (job #2415633) | Cod sursa (job #1521579) | Cod sursa (job #1668484) | Cod sursa (job #451590) | Cod sursa (job #1275980)
//package DEI;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Arrays;
class Main {
private static double dist(Punct p1, Punct p2) {
return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
}
private static double divide(int st, int dr, Punct[] array) {
if (dr - st <= 2) {
return Math.min(Math.min(dist(array[st], array[st + 1]), dist(array[st], array[st + 2])), dist(array[st + 1], array[st + 2]));
} else {
int m = (st + dr) / 2;
double d1 = Math.min(divide(st, m, array), divide(m, dr, array));
double d2 = d1;
for (int i = m; i >= st && array[m].x - array[i].x <= d1; i--)
for (int j = 1; j <= 7 && i + j <= dr; j++)
d2 = Math.min(d2, dist(array[i], array[i + j]));
return d2;
}
}
public static void main(String args[]) throws IOException {
// for (int j = 0; j < 10; j++) {
// for (int i = 1; i <= 10; i++) {
// System.out.println("Doing test: " + i);
// long startTime = System.currentTimeMillis();
int nrPuncte;
Punct[] array = null;
// long operationStartTime = System.currentTimeMillis();
BufferedReader br = new BufferedReader(new FileReader("cmap.in"));
String line = null;
nrPuncte = Integer.valueOf(br.readLine());
array = new Punct[nrPuncte];
Integer index = 0;
while ((line = br.readLine()) != null) {
double x = Double.valueOf(line.split(" ")[0]);
double y = Double.valueOf(line.split(" ")[1]);
array[index++] = new Punct(x, y);
}
// System.out.println("Read in: " + (System.currentTimeMillis() - operationStartTime));
// operationStartTime = System.currentTimeMillis();
Arrays.sort(array);
// System.out.println("Sort in: " + (System.currentTimeMillis() - operationStartTime));
// operationStartTime = System.currentTimeMillis();
PrintWriter g = new PrintWriter("cmap.out");
g.printf("%.6f\n", Math.sqrt(divide(0, nrPuncte - 1, array)));
// System.out.printf("%.6f\n", Math.sqrt(divide(0, nrPuncte - 1, array)));
g.close();
br.close();
// System.out.println("Solv in: " + (System.currentTimeMillis() - operationStartTime));
// System.out.println("Execution time: " + (System.currentTimeMillis() - startTime));
// }
// }
}
}
class Punct implements Comparable<Punct> {
double x, y;
public Punct() {
x = 0;
y = 0;
}
public Punct(double x, double y) {
this.x = x;
this.y = y;
}
@Override
public int compareTo(Punct a) {
if (x < a.x) {
if (y < a.y)
return -1;
else
return 1;
} else if (x > a.x) {
if (y < a.y)
return -1;
else
return 1;
}
return 0;
}
}