Cod sursa(job #1265685)

Utilizator miu.teoMiu Teodor miu.teo Data 17 noiembrie 2014 16:34:21
Problema Cele mai apropiate puncte din plan Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 2.54 kb
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();
	}
}
}