Pagini recente » Cod sursa (job #1347249) | Cod sursa (job #1236581) | Cod sursa (job #846082) | Istoria paginii runda/simulare_oji_9/clasament | Cod sursa (job #2265727)
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
private static final int UNDEFINED = -1;
static class Point {
long x, y;
Point(long x, long y) {
this.x = x;
this.y = y;
}
long distanceTo(Point that) {
return (this.x - that.x) * (this.x - that.x) + (this.y - that.y) * (this.y - that.y);
}
}
public static void main(String[] args) throws FileNotFoundException {
Scanner sc = new Scanner(new FileReader("cmap.in"));
PrintWriter pw = new PrintWriter("cmap.out");
// Scanner sc = new Scanner(System.in);
// int t = sc.nextInt();
// while (t-- > 0) {
List<Point> points = new ArrayList<>();
int n = sc.nextInt();
while (n-- > 0) {
long x = sc.nextInt();
long y = sc.nextInt();
points.add(new Point(x, y));
}
points.sort((p0, p1) -> {
int temp = Long.compare(p0.x, p1.x);
if (temp == 0) {
return Long.compare(p0.y, p1.y);
}
return temp;
});
double ans = Math.sqrt(getMinimumDistance(0, points.size() - 1, points));
pw.println(Math.floor(ans * 100000) / 100000);
// }
}
private static long getMinimumDistance(int left, int right, List<Point> points) {
if (right - left + 1 <= 3) {
long minDist = UNDEFINED;
for (int i = left; i < right; ++i) {
Point p0 = points.get(i);
for (int j = i + 1; j <= right; ++j) {
Point p1 = points.get(j);
if (minDist == UNDEFINED) {
minDist = p0.distanceTo(p1);
} else {
minDist = Math.min(minDist, p0.distanceTo(p1));
}
}
return minDist;
}
}
int mid = (left + right) >> 1;
long minDist0 = getMinimumDistance(left, mid, points);
long minDist1 = getMinimumDistance(mid + 1, right, points);
long minDist = Long.min(minDist0, minDist1);
Point splitPoint = points.get(mid);
List<Point> nearestPoints = new ArrayList<>();
for (int i = left; i <= right; ++i) {
Point p = points.get(i);
if (Math.abs(splitPoint.x - p.x) <= minDist) {
nearestPoints.add(p);
}
}
nearestPoints.sort((p0, p1) -> {
int temp = Long.compare(p0.y, p1.y);
if (temp == 0) {
return Long.compare(p0.x, p1.x);
}
return temp;
});
for (int i = 0; i < nearestPoints.size() - 1; ++i) {
Point p0 = nearestPoints.get(i);
for (int j = i + 1; j < nearestPoints.size() && j - i <= 7; ++j) {
Point p1 = nearestPoints.get(j);
minDist = Math.min(minDist, p0.distanceTo(p1));
}
}
return minDist;
}
}