Pagini recente » Istoria paginii runda/oji20091112/clasament | Cod sursa (job #1938477) | Cod sursa (job #2940488) | Cod sursa (job #486724) | Cod sursa (job #1276477)
import java.io.FileInputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;
class Punct implements Comparable<Punct> {
double x,y;
public Punct(double x, double y) {
super();
this.x = x;
this.y = y;
}
public double getX() {
return x;
}
public double getY() {
return y;
}
public double distanta(Punct a)
{
return (x-a.getX())*(x-a.getX())+(y-a.getY())*(y-a.getY());
}
public int compareTo(Punct o) {
if(y<o.y)
return -1;
if(y>o.y)
return 1;
return 0;
}
}
public class Main {
static Scanner sc;
static Punct[] p;
static PrintWriter iesire;
public static double divide(int s,int d)
{
if(d-s<=2)
{
if(d-s==2)
return Math.min(Math.min(p[s].distanta(p[s+1]), p[s].distanta(p[s+1])), p[s+1].distanta(p[s+2]));
else return Math.min(p[s].distanta(p[s+1]), p[s].distanta(p[s+1]));
}
int m= (s+d)/2;
double dist=Math.min(divide(s,m),divide(m+1,d));
double inter=dist;
for (int i = m; i >= s && p[m].getX() - p[i].getX() <= dist; i--)
for (int j = 1; j <= 7 && i + j <= d; j++)
inter = Math.min(inter, p[i].distanta(p[i + j]));
return inter;
}
public static void main(String[] args) throws Exception
{
sc=new Scanner(new FileInputStream("cmap.in"));
int n = sc.nextInt();
p = new Punct[n];
for(int i=0;i<n;i++)
{
int x = sc.nextInt();
int y = sc.nextInt();
p[i] = new Punct(x,y);
}
Arrays.sort(p);
iesire = new PrintWriter("cmap.out");
iesire.printf("%.6f" , Math.sqrt(divide(0,n-1)));
iesire.close();
}
}