Pagini recente » Cod sursa (job #2467467) | Arhiva de probleme | Cod sursa (job #2636755) | Cod sursa (job #1707379) | Cod sursa (job #1846834)
import java.io.*;
import java.util.*;
import java.lang.Math;
public class Main {
static class Point implements Comparable{
Double x, y;
Point(Double x, Double y) {
this.x = x;
this.y = y;
}
void swap(Point a) {
double x2 = x;
double y2 = y;
x = (double)a.x;
y = (double)a.y;
a.x = x2;
a.y = y2;
}
@Override
public int compareTo(Object val) {
Point baseVal = (Point)val;
return x.compareTo(baseVal.x);
}
}
public static double dist(Point a, Point b) {
return (double)(a.x - b.x) * (a.x - b.x) + (double)(a.y - b.y) * (a.y - b.y);
}
static long inf = ((long)1) << 60;
/* Demonstatia completa se afla pe pagina problemei.
Am implementat aceasta sursa si in C++, contul meu este Kira96.
*/
static double solve(Point[] points, int left, int right) {
if (left == right) {
return inf;
}
if (right - left == 1) {
if (points[left].y > points[right].y) {
points[left].swap(points[right]);
}
return dist(points[left], points[right]);
}
int mid = (left + right) / 2;
double midX = points[mid].x;
double sol = Math.min(solve(points, left, mid), solve(points, mid + 1, right));
int p1 = left;
int p2 = mid + 1;
ArrayList<Point> aux = new ArrayList<Point>();
ArrayList<Point> aux2 = new ArrayList<Point>();
for (; p1 <= mid && p2 <= right;) {
if (points[p1].y <= points[p2].y) {
if (midX - points[p1].x < sol) {
aux.add(points[p1]);
}
aux2.add(points[p1++]);
} else {
if (points[p2].x - midX < sol) {
aux.add(points[p2]);
}
aux2.add(points[p2++]);
}
}
for (; p1 <= mid; p1 += 1) {
if (midX - points[p1].x < sol) {
aux.add(points[p1]);
}
aux2.add(points[p1]);
}
for (; p2 <= right; p2 += 1) {
if (midX - points[p2].x < sol) {
aux.add(points[p2]);
}
aux2.add(points[p2]);
}
for (int i = 0; i < aux.size(); i += 1) {
int k = Math.min(aux.size(), i + 9);
for (int j = i + 1; j < k; j += 1) {
sol = Math.min(sol, dist(aux.get(i), aux.get(j)));
}
}
int t = 0;
for (int i = left; i <= right; i += 1) {
points[i] = aux2.get(t++);
}
return sol;
}
static final String in = "cmap.in";
static final String out = "cmap.out";
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new FileReader(in));
StringTokenizer stok;
final int n = Integer.parseInt(br.readLine());
Point[] points = new Point[n];
for (int i = 0; i < n; i += 1) {
stok = new StringTokenizer(br.readLine());
points[i] = new Point(Double.parseDouble(stok.nextToken()), Double.parseDouble(stok.nextToken()));
}
br.close();
Arrays.sort(points);
FileOutputStream fos = new FileOutputStream(out);
PrintWriter writer = new PrintWriter((OutputStream)fos);
writer.write(Math.sqrt(solve(points, 0, n - 1)) + "\n");
writer.close();
}
}