Pagini recente » Cod sursa (job #1258978) | Cod sursa (job #1373159) | Cod sursa (job #2170265) | Cod sursa (job #723065) | Cod sursa (job #1817571)
import java.io.*;
import java.util.*;
public class Main{
public static class Pair implements Comparable<Pair> {
int first,second;
public Pair(int first,int second){
this.first=first;
this.second=second;
}
public int compareTo(Pair other) {
return this.second-other.second;
}
public String toString(){
return "("+this.first+" "+this.second+")";
}
}
public static double dist(Pair p1,Pair p2){
return Math.sqrt((p1.first-p2.first)*(p1.first-p2.first)+
(p1.second-p2.second)*(p1.second-p2.second));
}
public static int mdl(int val){
if (val<0){
return -val;
} else {
return val;
}
}
public static double solve(ArrayList<Pair> p,int left,int right){
// System.out.println(left+" "+right);
if (right==left){
return Integer.MAX_VALUE-1;
}
if (right-left==1){
return dist(p.get(left),p.get(right));
}
ArrayList<Pair> midPoints=new ArrayList<>();
int dreaptaX=p.get((right+left)/2).first;
double lFasie=solve(p,left,(right+left)/2);
lFasie=Math.min(lFasie,solve(p,(right+left)/2+1,right));
for(int i=left;i<=right;i++){
if (mdl(dreaptaX-p.get(i).first)<lFasie){
midPoints.add(p.get(i));
}
}
Collections.sort(midPoints);
double result=lFasie;
for(int i=left;i<=right;i++){
for(int j=i+1;(i+j)<=right&&j-i<=7;++j){
result=Math.min(result,dist(p.get(i),p.get(j)));
}
}
return result;
}
public static void swap(Pair a,Pair b){
Pair temp;
temp=a;
a=b;
b=a;
}
public static void main(String[] Args){
ArrayList<Pair> p=new ArrayList<>();
try{
Scanner scanner=new Scanner(new File("cmap.in"));
int n=scanner.nextInt();
for(int i=1;i<=n;++i){
int aux1=scanner.nextInt();
int aux2=scanner.nextInt();
p.add(new Pair(aux2,aux1));
}
} catch(Exception e){
System.out.println(e.getMessage());
}
Collections.sort(p);
for(int i=0;i<p.size();++i){
p.set(i,new Pair(p.get(i).second,p.get(i).first));
}
try{
PrintWriter writer = new PrintWriter("cmap.out", "UTF-8");
writer.println(solve(p,0,p.size()-1));
writer.close();
} catch (IOException e) {
// do something
}
}
}