Pagini recente » Cod sursa (job #2858053) | Cod sursa (job #212318) | Cod sursa (job #2643540) | Cod sursa (job #1684390) | Cod sursa (job #1847569)
import java.util.*;
import java.io.*;
class Point implements Comparable<Point>{
int x, y;
Point() {}
Point(Scanner scanner) {
x = scanner.nextInt();
y = scanner.nextInt();
}
public static double distance(Point a, Point b) {
double dx = a.x - b.x;
double dy = a.y - b.y;
return dx * dx + dy * dy;
}
public int compareTo(Point other) {
if (x < other.x) return -1;
if (x == other.x) return 0;
return 1;
}
}
class Main {
private static int n;
private static Point[] points;
private static Point[] aux;
private static Point[] middlePoints;
public static void main(String[] args) {
try {
File inputFile = new File("cmap.in");
File outputFile = new File("cmap.out");
FileInputStream inputStream = new FileInputStream(inputFile);
Scanner scanner = new Scanner(inputStream);
readData(scanner);
scanner.close();
inputStream.close();
FileOutputStream outputStream = new FileOutputStream(outputFile);
PrintWriter writer = new PrintWriter(outputStream);
Arrays.sort(points);
writer.print(Math.sqrt(getClosestPair(0, n - 1)));
writer.print('\n');
writer.close();
outputStream.close();
} catch(IOException e) {};
}
private static void readData(Scanner scanner) {
n = scanner.nextInt();
points = new Point[n];
aux = new Point[n];
middlePoints = new Point[n];
for (int i = 0; i < n; i++)
points[i] = new Point(scanner);
}
private static int interclaseaza(int x, double d, int start, int end) {
int mid = (start + end) / 2;
int i = start;
int j = mid + 1;
int k = 0;
int middlePointsCount = 0;
while (i <= mid && j <= end) {
if (points[i].y <= points[j].y) {
if (x - points[i].x < d)
middlePoints[middlePointsCount++] = points[i];
aux[k++] = points[i++];
}
else {
if (points[j].x - x < d)
middlePoints[middlePointsCount++] = points[j];
aux[k++] = points[j++];
}
}
for (; i <= mid; i++) {
aux[k++] = points[i];
if (x - points[i].x < d)
middlePoints[middlePointsCount++] = points[i];
}
for (; j <= end; j++) {
aux[k++] = points[j];
if (points[j].x - x < d)
middlePoints[middlePointsCount++] = points[j];
}
for (int l = 0; l < k; l++)
points[start + l] = aux[l];
return middlePointsCount;
}
private static double getClosestPair(int start, int end) {
if (start + 1 == end) {
if (points[end].y < points[start].y) {
Point aux = points[end];
points[end] = points[start];
points[start] = aux;
}
return Point.distance(points[start], points[end]);
}
if (start >= end) return Point.distance(points[0], points[1]);
int mid = (start + end) / 2;
int middleX = points[mid].x;
double sol = Math.min(
getClosestPair(start, mid),
getClosestPair(mid + 1, end)
);
int k = interclaseaza(middleX, sol, start, end);
for (int i = 0; i < k; i++) {
int lim = Math.min(i + 8, k - 1);
for (int j = i + 1; j <= lim; j++)
sol = Math.min(sol, Point.distance(middlePoints[i], middlePoints[j]));
}
return sol;
}
}