Pagini recente » infoarena - comunitate informatica, concursuri de programare | Cod sursa (job #1282050) | infoarena - comunitate informatica, concursuri de programare | infoarena - comunitate informatica, concursuri de programare | Cod sursa (job #1282188)
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.ArrayList;
import java.util.Comparator;
class Main {
static int nrPuncte;
static Punct[] array ;
//static Punct[] copyOfSortedArray ;
// static Punct[] aux ;
static long dist(Punct A, Punct B){
long x= B.x - A.x,y=B.y - A.y;
return x*x+y*y;
}
static void merge( int st, int dr ){
int mid = (st + dr) / 2, p1 = st, p2 = mid + 1, len = 0;
Punct aux[]=new Punct[dr-st+2];
while (p1 <= mid && p2 <= dr)
if (array[p1].x < array[p2].x)
aux[++len] = array[p1++];
else
aux[++len] = array[p2++];
while (p1 <= mid)
aux[++len] = array[p1++];
while (p2 <= dr)
aux[++len] = array[p2++];
System.arraycopy(aux,1,array,st,dr-st+1);
// for (int i = st, j = 1; i <= dr; ++i, ++j)
// array[i] = aux[j];
}
static long divide(int st, int dr){
long res = Long.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;
int xmid=array[mid].x;
res = Math.min(divide(st, mid), divide(mid + 1, dr));
merge(st, dr);
ArrayList<Punct> aux=new ArrayList<Punct>();
int len = 0;
for (int i = st; i <= dr; ++i)
if (Math.abs(array[i].x - xmid) < res) //< nu <=
aux.add( array[i]);
for (int i = 1; i < len; ++i)
for (int j = i + 1; j <= len &&j-i<8; ++j) //len, nu aux.length
res = Math.min(res, dist(aux.get(i), aux.get(j)));
return res;
}
public static void main(String args[]) throws NumberFormatException, IOException{
// long time = System.currentTimeMillis();
BufferedReader br = new BufferedReader(new FileReader("cmap.in"));
nrPuncte = Integer.parseInt(br.readLine());
array = new Punct[nrPuncte+1];
//aux = new Punct[nrPuncte+1];
// copyOfSortedArray = new Punct[nrPuncte+1];
String cline[];
int x,y;
for (int index = 1 ; index<=nrPuncte; index++) {
cline=br.readLine().split(" ");
x = Integer.parseInt(cline[0]);
y = Integer.parseInt(cline[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;
return 0;
}
});
// System.arraycopy(array,1,copyOfSortedArray,1,nrPuncte);
// 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();
// long timp = System.currentTimeMillis() - time;
// System.out.println("Time:"+timp+"ms");
}
}
class Punct implements Comparable<Punct>{
int x,y;
public Punct(int x, int y) {
this.x = x;
this.y = y;
}
public Punct() {
}
@Override
public int compareTo(Punct o) {
if(y < o.y)
return -1;
if(y > o.y)
return 1;
return 0;
}
}