Pagini recente » Cod sursa (job #1976623) | Cod sursa (job #1603187) | Borderou de evaluare (job #1832912) | Cod sursa (job #2864623) | Cod sursa (job #1850297)
import java.util.*;
import java.io.*;
class Punct {
private int x,y;
public Punct()
{
setX(0);
setY(0);
}
public Punct(int a, int b)
{
setX(a);
setY(b);
}
public int getX() {
return x;
}
public void setX(int x) {
this.x = x;
}
public int getY() {
return y;
}
public void setY(int y) {
this.y = y;
}
}
class Main {
private static Scanner s;
public static double distanta(Punct a, Punct b)
{
return Math.sqrt((a.getX()-b.getX())*(a.getX()-b.getX())+(a.getY()-b.getY())*(a.getY()-b.getY()));
}
static double gasireScurta(ArrayList<Punct> pct, int n)
{
double min=Double.MAX_VALUE;
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
min=distanta(pct.get(i),pct.get(j));
return min;
}
static double bandaApropiate(ArrayList<Punct> p,int n,double d)
{
double min=d;
for(int i=0;i<n;i++)
for(int j=i+1;j<n && (p.get(j).getY()-p.get(i).getY())<min;j++)
min=distanta(p.get(i),p.get(j));
return min;
}
static double gasesteApropiate(ArrayList<Punct> pctX, ArrayList<Punct> pctY,int n)
{
if(n<=3)return gasireScurta(pctX,n);
int m=n/2;
Punct mijloc=pctX.get(m);
ArrayList<Punct> stanga=new ArrayList<Punct>();
ArrayList<Punct> dreapta=new ArrayList<Punct>();
int istg=0,idr=0;
for(int i=0;i<pctY.size();i++)
{
if(pctY.get(i).getX()<=mijloc.getX()){
stanga.add(pctY.get(i));
istg++;
}
else{
dreapta.add( pctY.get(i));
idr++;
}
}
ArrayList<Punct> aux=new ArrayList<Punct>();
for(int i=m;i<pctX.size();i++)
{
aux.add(pctX.get(i));
}
double stg=gasesteApropiate(pctX,stanga,m);
double dr=gasesteApropiate(aux,dreapta,n-m);
double d=Math.min(dr,stg);
ArrayList<Punct> banda=new ArrayList<Punct>();
int j=0;
for(int i=0;i<pctY.size();i++)
if(Math.abs(pctY.get(i).getX()-mijloc.getX())<d)
{
banda.add(pctY.get(i));
j++;
}
return Math.min(d, bandaApropiate(banda,j,d));
}
static double celeMaiApropiate(ArrayList<Punct> pct,int n)
{
ArrayList<Punct> pctX=new ArrayList<Punct>();
ArrayList<Punct> pctY=new ArrayList<Punct>();
for(int i=0;i<n;i++)
{
pctX.add(pct.get(i));
pctY.add(pct.get(i));
}
Arrays.sort(pctX,new Comparator<Punct>(){
public int compare(Punct a, Punct b)
{
return a.getX()-b.getX();
}
});
Arrays.sort(pctY,new Comparator<Punct>(){
public int compare(Punct a, Punct b)
{
return a.getY()-b.getY();
}
});
return gasesteApropiate(pctX,pctY,n);
}
public static void main(String[] args)
{
try {
s = new Scanner(new File("date.in"));
int n=s.nextInt();
ArrayList<Punct> puncte=new ArrayList<Punct>();
for(int i=0;i<n;i++)
{
Punct p=new Punct(s.nextInt(),s.nextInt());
puncte.add(p);
}
double result=celeMaiApropiate(puncte,n);
PrintWriter w=new PrintWriter("date.out");
w.println(result);
w.close();
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}