Pagini recente » Cod sursa (job #2220592) | Istoria paginii runda/simulare_emag_mediu_2016_runda1/clasament | Istoria paginii runda/lanitam_urtimud/clasament | Rating Radu Cristian (white_tiger_radu) | Cod sursa (job #1276221)
package DistantaMinimaPuncte;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.Scanner;
class Punct implements Comparable<Punct>{
long x, y;
public double dist(Punct P){
return Math.sqrt(Math.pow(x-P.x, 2)+Math.pow(y-P.y,2));
}
Punct(long a, long b){
x=a;
y=b;
}
@Override
public int compareTo(Punct P) {
if(x==P.x)
return (int)(y-P.y);
return (int)(x-P.x);
}
}
class Main {
static Punct V[], A;
static double dmin=Double.MAX_VALUE;
static void mediana(int a, int b, int k)
{
int i=a, j=b;
Punct p=V[(a+b)/2];
while(i <= j)
{
while(V[i].compareTo(p)<0) i++;
while(V[j].compareTo(p)>0) j--;
if(i <= j)
{
Punct aux = V[i];
V[i] = V[j];
V[j] = aux;
i++;
j--;
}
}
if (k <= j) mediana(a,j,k);
else if (k >= i) mediana(i,b,k);
}
static void Search(int p, int u){
if((u-p+1)>1){
int poz=(u-p+1)/2+p;
mediana(p, u, poz);
if(A.compareTo(V[poz])==0);
else{
if(V[poz].dist(A)<dmin){
dmin=V[poz].dist(A);
}
if(A.compareTo(V[poz])<0)
Search(p,poz-1);
else if(A.compareTo(V[poz])>0)
Search(poz+1, u);
}
}
else
if(A.compareTo(V[p])==0);
else
if(V[p].dist(A)<dmin){
dmin=V[p].dist(A);
}
}
public static void main(String[] args) throws FileNotFoundException {
Scanner sc=new Scanner(new File("cmap.in"));
long n= sc.nextLong();
V= new Punct[(int) n];
for(int i=0; i<n;i++)
V[i]= new Punct(sc.nextLong(), sc.nextLong());
for(int i=0;i<n;i++){
A=new Punct(V[i].x, V[i].y);
Search(0,(int) (n-1));
}
PrintWriter pr= new PrintWriter(new File("cmap.out"));
pr.print(dmin);
sc.close();
pr.close();
}
}