Pagini recente » Cod sursa (job #3210750) | Cod sursa (job #1353097) | Cod sursa (job #3214658) | Cod sursa (job #1406133) | Cod sursa (job #1821402)
import java.io.File;
import java.io.*;
import java.util.*;
class p4{
public static void main(String args[]) throws IOException{
try (Writer pw = new BufferedWriter(new OutputStreamWriter(new FileOutputStream("cmap.out"), "utf-8"))) {
Scanner sc = new Scanner(System.in);
Scanner sci = new Scanner( new File("cmap.in"));
class plan{
class pair{
int x,y;
}
int n;
double rez = 1000.0;
ArrayList<pair> v;
ArrayList<pair> vy;
plan(){
n = sci.nextInt();
v = new ArrayList<pair>();
vy = new ArrayList<pair>();
for(int i=0;i<n;i++){
pair aux = new pair();
aux.x = sci.nextInt();
aux.y = sci.nextInt();
v.add(aux);
vy.add(aux);
}
Collections.sort(v, (a, b) -> a.x - b.x);
Collections.sort(vy, (a, b) -> a.y - b.y);
}
double getMinDist(int l, int r, ArrayList<pair> vy){
//System.out.println(vy.size()+ "++++++++++++++++++++++++++++++++++++++++++");
if(l == r){ ///probabil nu o sa intre pe ramura asta :-?
return 0;
}
if(r - l == 1){
double aux = (v.get(l).x-v.get(r).x)*(v.get(l).x-v.get(r).x) + (v.get(l).y-v.get(r).y)*(v.get(l).y-v.get(r).y);
return Math.sqrt(aux);
}
if(r-l == 2){
double aux = Math.sqrt((v.get(l+1).x-v.get(r).x)*(v.get(l+1).x-v.get(r).x) + (v.get(l+1).y-v.get(r).y)*(v.get(l+1).y-v.get(r).y));
double bux = Math.sqrt((v.get(l).x-v.get(r-1).x)*(v.get(l).x-v.get(r-1).x) + (v.get(l).y-v.get(r-1).y)*(v.get(l).y-v.get(r-1).y));
double cux = Math.sqrt((v.get(l).x-v.get(r).x)*(v.get(l).x-v.get(r).x) + (v.get(l).y-v.get(r).y)*(v.get(l).y-v.get(r).y));
return Math.min(aux,Math.min(bux,cux));
}
int mid = (l+r)/2;
ArrayList<pair> vly = new ArrayList<pair>();
ArrayList<pair> vry = new ArrayList<pair>();
for(int i = 0;i<vy.size();i++){
if(vy.get(i).x <= v.get(mid).x){
vly.add(vy.get(i));
}else{
vry.add(vy.get(i));
}
}
double lmin = getMinDist(l, mid, vly);
double rmin = getMinDist(mid +1, r, vry);
double dmin = Math.min(lmin, rmin);
ArrayList<pair> LY = new ArrayList<pair>();
for(int i=0;i<vy.size();i++){
if((vy.get(i).x <= v.get(mid).x + dmin) && (v.get(mid).x - dmin <= vy.get(i).x)){
LY.add(vy.get(i));
}
}
for(int i=0;i<LY.size();i++){
for(int j=i+1; j<=7 && j<LY.size(); j++){
double aux = Math.sqrt((LY.get(i).x - LY.get(j).x)*(LY.get(i).x - LY.get(j).x) + (LY.get(i).y - LY.get(j).y)*(LY.get(i).y - LY.get(j).y));
//System.out.println("kek "+rez+" "+LY.get(i).x+" "+LY.get(i).y+" "+LY.get(j).x+" "+LY.get(j).y);
rez = Math.min(rez, aux);
}
}
return Math.min(rez,dmin);
}
}
plan a = new plan();
pw.write(""+a.getMinDist(0, a.n-1,a.vy));
pw.close();
}
catch(Exception e){
System.out.println(""+e);
}
}
}