Cod sursa(job #1821402)

Utilizator EhtRalpmetFMI Ardei Claudiu-Alexandru EhtRalpmet Data 3 decembrie 2016 01:04:05
Problema Cele mai apropiate puncte din plan Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 3.01 kb
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);
		}
	}
}