Pagini recente » Cod sursa (job #2748444) | Cod sursa (job #1265685)
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;
class Punct{
double x,y;
Punct(double x,double y){
this.x=x;
this.y=y;
}
double dist(Punct A){
return Math.sqrt((x-A.x)*(x-A.x)+(y-A.y)*(y-A.y));
}
}
class sortX implements Comparator<Punct>{
public int compare(Punct one, Punct another){
int returnVal = 0;
if(one.x < another.x){
returnVal = -1;
}else if(one.x > another.x){
returnVal = 1;
}else if(one.x == another.x){
returnVal = 0;
}
return returnVal;
}
}
class sortY implements Comparator<Punct>{
public int compare(Punct one,Punct another){
if(one.y>another.y)
return 1;
if(one.y<another.y)
return -1;
return 0;
}
}
public class mainClass {
static double minimPct(ArrayList<Punct> X,int s,int d){
double min=X.get(s).dist(X.get(s+1));
//min=Double.POSITIVE_INFINITY;
for(int i=s;i<d;i++){
for(int j=i+1;j<=d;j++)
if(X.get(i).dist(X.get(j))<min)
min=X.get(i).dist(X.get(j));
}
return min;
}
static double divImp(ArrayList<Punct>X,ArrayList<Punct> Y,int st,int dr){
if((dr-st)<=3)
return minimPct(X,st,dr);
else{
double d1,d2;
ArrayList<Punct>xIntY=new ArrayList<>();
int m=(st+dr)/2;
d1=divImp(X,Y,st,m);
d2=divImp(X,Y,m+1,dr);
double d=Math.min(d1, d2);
for(int i=st;i<=dr;i++)
if(Math.abs(X.get(dr).x-Y.get(i).x)<d)
xIntY.add(Y.get(i));
for(int i=0;i<xIntY.size();i++){
int raza=Math.min(xIntY.size(),i+8);
for(int j=i+1;j<raza;j++)
d=Math.min(d,xIntY.get(i).dist(xIntY.get(j)));
}
return d;
}
}
public static void main(String[] arg){
File f=new File("cmap.in");
try{
Scanner sc=new Scanner(f);
double x,y;
int n=sc.nextInt();
ArrayList<Punct> X,Y;
X=new ArrayList<Punct>();
Y=new ArrayList<Punct>();
for(int i=0;i<n;i++){
x=sc.nextDouble();
y=sc.nextDouble();
X.add(new Punct(x,y));
Y.add(new Punct(x,y));
}
Collections.sort(X,new sortX());
Collections.sort(Y,new sortY());
double d=divImp(X,Y,0,n-1);
PrintStream out = new PrintStream(new FileOutputStream("cmap.out"));
out.print("sa");
sc.close();
out.close();
}
catch(FileNotFoundException e){
e.printStackTrace();
}
}
}