Pagini recente » Cod sursa (job #3280708) | Cod sursa (job #2775299) | Cod sursa (job #313331) | Cod sursa (job #1047461) | Cod sursa (job #1289894)
import java.io.FileInputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static Scanner sc;
static Punct[] p,copy;
static PrintWriter iesire;
static int n;
static void Merge(int st,int dr)
{
Punct aux[] = new Punct[dr-st+1];
int m=(st+dr)/2;
int i=st,j=m+1,k=0;
while(i<=m && j<=dr)
{
if(p[i].getX()<p[j].getX())
{
aux[k++]=p[i++];
}
else
{
aux[k++]=p[j++];
}
}
while(i<=m)
{
aux[k++]=p[i++];
}
while(j<=dr)
{
aux[k++]=p[j++];
}
for(i=st,k=0;i<=dr;i++,k++)
{
p[i]=aux[k];
}
}
static double divide(int s,int d)
{
Punct aux[] = new Punct[d-s+1];
if(d-s<=2)
{
Merge(s,d-1);
Merge(s,d);
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;
Merge(s,d);
int k=0;
for(int i=s;i<=d;i++)
{
if(Math.abs(p[i].getY()-copy[m].getY())<inter)
{
aux[k++]=p[i];
}
}
for(int i=0;i<k-1;i++)
{
for(int j=i+1;j<k && j-i<=8;j++)
{
inter=Math.min(inter, p[i].distanta(p[j]));
}
}
return inter;
}
public static void main(String[] args) throws Exception
{
sc=new Scanner(new FileInputStream("cmap.in"));
n = sc.nextInt();
p = new Punct[n];
copy = 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);
for(int i=0;i<n;i++)
{
copy[i]=p[i];
}
iesire = new PrintWriter("cmap.out");
iesire.printf("%.6f" , Math.sqrt(divide(0,n-1)));
iesire.close();
}
}
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 String toString()
{
return "[" + x + "," + y + "] ";
}
}