Pagini recente » Cod sursa (job #1953552) | Cod sursa (job #2026993) | Cod sursa (job #2651546) | Cod sursa (job #1731349) | Cod sursa (job #1275374)
import java.io.FileNotFoundException;
import java.util.*;
class customComparator implements Comparator<Punct>
{
public int compare(Punct p1, Punct p2)
{
return p1.inainte(p2);
}
}
class Punct
{
private double x;
private double y;
public void setX(double value)
{
x=value;
}
public void setY(double value)
{
y=value;
}
public double getX()
{
return x;
}
public double getY()
{
return y;
}
public Punct(double val1, double val2)
{
x=val1;
y=val2;
}
public int inainte(Punct p)
{
if(x<p.getX()) return 1;
else if(x==p.getX() && y<p.getY()) return 1;
else return 0;
}
public double distanta(Punct p)
{
return Math.sqrt((p.getX()-x)*(p.getX()-x)+(p.getY()-y)*(p.getY()-y));
}
}
class Apropiate
{
static int n;
static List<Punct> puncte = new ArrayList<Punct>();
public static void main(String args[])
{
Apropiate t = new Apropiate();
t.citire();
t.sort();
System.out.println(t.divide(0,n-1));
}
private double divide(int stg, int dr)
{
if(dr-stg > 2)
{
double min1 = divide(stg, (stg+dr)/2);
double min2 = divide((stg+dr)/2+1,dr);
if(min1>min2)
min1 = min2;
int i = (stg+dr)/2;
Punct p1,p2;
p1 = new Punct(0,0);
p2 = new Punct(0,0);
while( i>=stg && puncte.get(i).getX() > (stg+dr)/2-min1)
{
p1 = puncte.get(i);
int j = (stg+dr)/2 + 1;
while(j<=dr && puncte.get(j).getX()<(stg+dr)/2 + min1)
{
p2 = puncte.get(j);
if(p1.distanta(p2)< min1)
min1 = p1.distanta(p2);
j++;
}
i--;
}
return min1;
}
else if(dr-stg == 1)
return puncte.get(dr).distanta(puncte.get(stg));
else
{
double d = puncte.get(dr).distanta(puncte.get(stg));
if(d > puncte.get(dr).distanta(puncte.get(stg+1)))
d = puncte.get(dr).distanta(puncte.get(stg+1));
if(d > puncte.get(dr-1).distanta(puncte.get(stg)))
d = puncte.get(dr-1).distanta(puncte.get(stg));
return d;
}
}
private void citire()
{
try
{
Scanner fcin = new Scanner(new java.io.File("ex.in"));
n=fcin.nextInt();
for(int i=0;i<n;i++)
puncte.add(new Punct(fcin.nextDouble(),fcin.nextDouble()));
}
catch(FileNotFoundException fnf)
{
System.out.println("Fisier inexistent");
}
}
private void sort()
{
Collections.sort(puncte, new customComparator());
}
}