Pagini recente » Cod sursa (job #3243810) | Cod sursa (job #1727383) | Cod sursa (job #2178194) | Cod sursa (job #2197687) | Cod sursa (job #1542035)
import java.util.*;
import java.io.*;
class P5
{
static Punct[] punct;
static double getMin(int start, int end)
{
double minSt, minDr, minD;
if(end - start <= 2) //daca avem cel putin trei elemente
{
double[] mins = new double[end-start+1];
double min = -1;
int i, j=0;
for(i = start; i <= end; i++)
for(j = i+1; j<=end; j++)
if(min == -1 || punct[i].distance(punct[j]) < min)
min = punct[i].distance(punct[j]);
return min;
}
minSt = getMin(start, (start+end)/2);
minDr = getMin((start+end)/2+1, end);
minD = minSt < minDr ? minSt : minDr;
Punct[] db = new Punct[punct.length];
int ndb = 0;
for(int i = start; i <= end; i++)
if(Math.abs(punct[i].x - punct[(start+end)/2].x) < minD)
db[ndb++] = punct[i];
Arrays.sort(db, 0, ndb, new Comparator<Punct>(){
public int compare(Punct a, Punct b)
{
double d = a.y-b.y;
if (d < 0)
return -1;
if(d > 0)
return 1;
return 0;
}
});
for(int i = 0; i < ndb; i++)
for(int j = i+1; j < ndb; j++)
if(db[i].distance(db[j]) < minD)
minD = db[i].distance(db[j]);
return minD;
}
public static void main(String argsp[])
{
int n, a, b;
try
{
Scanner sc = new Scanner(new File("cmap.in"));
PrintWriter wr = new PrintWriter("cmap.out");
n = sc.nextInt();
punct = new Punct[n];
for(int i = 0; i<n; i++)
punct[i] = new Punct(sc.nextInt(), sc.nextInt());
sc.close();
Arrays.sort(punct, new Comparator<Punct>(){
@Override
public int compare(Punct a, Punct b)
{
if(a.x - b.x < 0)
return -1;
if(a.x - b.x > 0)
return 1;
return 0;
}
});
wr.print(getMin(0, n-1));
wr.close();
}
catch(IOException ioex)
{
System.out.println(ioex.getMessage());
}
}
}
class Punct
{
double x, y;
public Punct(double x, double y)
{
this.x = x;
this.y = y;
}
public double distance(Punct p)
{
return Math.sqrt((x-p.x)*(x-p.x) + (y-p.y)*(y-p.y));
}
}