Pagini recente » Cod sursa (job #3140664) | Cod sursa (job #3041024) | Cod sursa (job #1491484) | Cod sursa (job #2862028) | Cod sursa (job #1847519)
import java.util.*;
import java.io.*;
class Point implements Comparable<Point>{
double x, y;
Point() {}
Point(Scanner scanner) {
x = scanner.nextDouble();
y = scanner.nextDouble();
}
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(double 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];
for (; j <= end; j++) aux[k++] = 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 0x3fffffff;
int mid = (start + end) / 2;
double 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++)
for (int j = i + 1; j < Math.min(k, i + 8 + 1); j++)
sol = Math.min(sol, Point.distance(middlePoints[i], middlePoints[j]));
return sol;
}
}