Pagini recente » Monitorul de evaluare | Monitorul de evaluare | Istoria paginii utilizator/razviyagalo | Cod sursa (job #1016502) | Cod sursa (job #1276469)
import java.io.*;
import java.util.*;
class Punct implements Comparable<Punct> {
int x,y;
public Punct(int x, int y) {
super();
this.x = x;
this.y = y;
}
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;
}
public int 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 int 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;
int dist=Math.min(divide(s,m),divide(m+1,d));
int 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;
/*
for(int i=s;i<m;i++)
{
if(p[i].distanta(p[m])<dist)
{
ps[ns++]= p[i];
}
}
for(int i=m+1;i<=d;i++)
{
if(p[i].distanta(p[m])<dist)
{
pd[nd++]= p[i];
}
}
for(int i=0;i<ns;i++)
for(int j=0;j<nd;j++)
{
inter=Math.min(ps[i].distanta(pd[j]), inter);
}
*/
}
public static void main(String[] args) throws Exception
{
sc=new Scanner(new java.io.File("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);
//System.out.println(Math.sqrt(divide(0,n-1)));
iesire = new PrintWriter("cmap.out");
iesire.printf("%.6f" , Math.sqrt(divide(0,n-1)));
iesire.close();
}
}