Pagini recente » Cod sursa (job #1523556) | Cod sursa (job #2190382) | Cod sursa (job #2437281) | Cod sursa (job #1306138) | Cod sursa (job #1276617)
//package cmap;
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
class Main {
static int nrPuncte;
static Punct[] array = null;
static Punct[] copyOfSortedArray = null;
static Punct[] aux = null;
static double dist(Punct A, Punct B){
return ( B.x - A.x ) * ( B.x - A.x ) + ( B.y - A.y ) * ( B.y - A.y );
}
static void merge( int st, int dr ){
int mid = (st + dr) / 2, p1 = st, p2 = mid + 1, len = 0;
while (p1 <= mid || p2 <= dr)
if (p1 > mid)
aux[++len] = array[p2++];
else if (p2 > dr)
aux[++len] = array[p1++];
else if (array[p1].x < array[p2].x)
aux[++len] = array[p1++];
else
aux[++len] = array[p2++];
for (int i = st, j = 1; i <= dr; ++i, ++j)
array[i] = aux[j];
}
static double divide(int st, int dr){
double res = Double.MAX_VALUE;
if (dr - st <= 2) {
for (int i = st; i <= dr; ++i)
for (int j = i + 1; j <= dr; ++j)
res = Math.min(res, dist(array[i], array[j]));
Arrays.sort(array, st, dr+1);
return res;
}
int mid = (st + dr) / 2;
res = Math.min(divide(st, mid), divide(mid + 1, dr));
merge(st, dr);
int len = 0;
for (int i = st; i <= dr; ++i)
if (Math.abs(array[i].x - copyOfSortedArray[mid].x) <= res)
aux[++len] = array[i];
for (int i = 1; i < len; ++i)
for (int j = i + 1, cnt = 1; cnt <= 7 && j < aux.length; ++j, ++cnt)
res = Math.min(res, dist(aux[i], aux[j]));
return res;
}
public static void main(String args[]) throws NumberFormatException, IOException{
BufferedReader br = new BufferedReader(new FileReader("cmap.in"));
nrPuncte = Integer.valueOf(br.readLine());
array = new Punct[nrPuncte+1];
aux = new Punct[nrPuncte+1];
copyOfSortedArray = new Punct[nrPuncte+1];
String line = null;
for (int index = 1 ; (line = br.readLine()) != null; index++) {
double x = Integer.valueOf(line.split(" ")[0]);
double y = Integer.valueOf(line.split(" ")[1]);
array[index] = new Punct(x, y);
aux[index] = new Punct();
}
br.close();
Arrays.sort(array,1,nrPuncte, new Comparator<Punct>() {
@Override
public int compare(Punct o1, Punct o2) {
if(o1.x < o2.x)
return -1;
if(o1.x > o2.x)
return 1;
if(o1.x < o2.x)
return -1;
if(o1.y > o2.y)
return 1;
return 0;
}
});
for(int index = 1; index <= nrPuncte;index++ ){
copyOfSortedArray[index] = new Punct(array[index].x, array[index].y);
}
PrintWriter printer = new PrintWriter("cmap.out");
printer.printf("%.6f\n", Math.sqrt(divide(1, nrPuncte)));
printer.close();
}
}
class Punct implements Comparable<Punct>{
double x,y;
public Punct(double x, double y) {
this.x = x;
this.y = y;
}
public Punct() {
x=0;
y=0;
}
@Override
public int compareTo(Punct o) {
if(y < o.y)
return -1;
if(y > o.y)
return 1;
return 0;
}
}