Pagini recente » Cod sursa (job #79795) | Cod sursa (job #1272427) | Cod sursa (job #1938439) | Cod sursa (job #3126322) | Cod sursa (job #1542157)
import java.util.*;
import java.io.*;
class Main
{
static Punct[] punct;
static long getMin(int start, int end, Punct[] ySorted)
{
long minSt, minDr, minD;
if(end - start <= 2) //daca avem cel putin trei elemente
{
long 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]);
for(i = start; i <= end; i++)
ySorted[i] = punct[i];
for(i = start; i < end; i++)
{
int _min = i;
Punct aux;
for(j = i+1; j <= end; j++)
if(ySorted[j].y < ySorted[_min].y)
_min = j;
if(_min != i)
{
aux = ySorted[i];
ySorted[i] = ySorted[_min];
ySorted[_min] = aux;
}
}
return min;
}
Punct[] tmp = new Punct[end-start+1];
minSt = getMin(start, (start+end)/2, ySorted);
minDr = getMin((start+end)/2+1, end, ySorted);
minD = minSt < minDr ? minSt : minDr;
int nTmp = 0, a=start, b=(start+end)/2+1;
while(a <= (start+end)/2 && b <= end)
if(ySorted[a].y < ySorted[b].y)
tmp[nTmp++] = ySorted[a++];
else
tmp[nTmp++] = ySorted[b++];
while(a <= (start+end)/2)
tmp[nTmp++] = ySorted[a++];
while(b <= end)
tmp[nTmp++] = ySorted[b++];
for(int i = start; i <= end; i++)
ySorted[i] = tmp[i-start];
Punct[] db = new Punct[tmp.length];
int ndb = 0;
for(int i = 0; i < tmp.length; i++)
if(Math.abs(tmp[i].x - punct[(start+end)/2].x) < minD)
db[ndb++] = tmp[i];
for(int i = 0; i < ndb; i++)
for(int j = i+1; j < ndb && j <= i+7; j++)
if(db[i].distance(db[j]) < minD)
minD = db[i].distance(db[j]);
return minD;
}
public static void main(String argsp[])
{
int n;
try
{
FileInputStream fis = new FileInputStream("cmap.in");
Scanner sc = new Scanner((InputStream)fis);
FileOutputStream fos = new FileOutputStream("cmap.out");
PrintWriter wr = new PrintWriter((OutputStream)fos);
Punct[] s;
n = sc.nextInt();
punct = new Punct[n];
s = new Punct[n];
for(int i = 0; i<n; i++)
punct[i] = new Punct(sc.nextLong(), sc.nextLong());
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(Math.sqrt(getMin(0, n-1, s)));
wr.close();
}
catch(IOException ioex)
{
System.out.println(ioex.getMessage());
}
}
}
class Punct
{
long x, y;
public Punct(long x, long y)
{
this.x = x;
this.y = y;
}
public long distance(Punct p)
{
return (x-p.x)*(x-p.x) + (y-p.y)*(y-p.y);
}
}