Cod sursa(job #1820487)

Utilizator AllenWalkerAllen Walker AllenWalker Data 1 decembrie 2016 20:00:48
Problema Cele mai apropiate puncte din plan Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 3.28 kb
import java.io.*;
import java.util.*;


 class Point implements Comparable<Point>{
	int x;
	int y;
	
	public Point(int x, int y){
		this.x = x;
		this.y = y;
	}
	
	public String toString(){
		return "[" + x + ", " + y + "]";
	}
	
	public int compareTo(Point other){
		return this.x - other.x;
	}
}


public class Main {
	
	public static ArrayList<Point> points =  new ArrayList<Point>();
	public static ArrayList<Point> pointsAux =  new ArrayList<Point>();
	public static ArrayList<Point> pointsMerged =  new ArrayList<Point>();
	
	public static double dist(Point A, Point B){
			return Math.sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
	}
	
	public static double solveForThree(int ls, int ld){
		if(ls == ld)
			return 0;
		double minDist = dist(points.get(ls), points.get(ls + 1));
		double distance = 0;
		for(int i = ls; i <= ld; i ++)
			for(int j = ls + 1; j <= ld; j ++)
			if(!points.get(i).equals(points.get(j))){
				distance = dist(points.get(i), points.get(j));
				if(distance < minDist)
					minDist = distance;
			}
		return minDist;
		
	}

	public static double getShortestDistance(int ls, int ld){
		if(ld - ls + 1 <= 3)
			return solveForThree(ls, ld);
		else{
			int m = (ls + ld)/2;
			double distStg = getShortestDistance(ls, m);
			double distDr = getShortestDistance(m + 1, ld);
			double distMin = Math.min(distStg, distDr);
			
			for(int i = ls; i <= ld; i ++){
				int dr = points.get(m).x;
				Point current = points.get(i);
				if(Math.abs(current.x - dr) < distMin)
					pointsAux.add(current);
			}
				
			merge(pointsAux, pointsMerged);
			
			for(int i = 0; i < pointsMerged.size(); i ++){			
				int maxIndex = Math.min(pointsMerged.size(),7);
				for(int j = 0; j <maxIndex; j ++)
					if(!pointsMerged.get(i).equals(pointsMerged.get(j)))
						distMin = Math.min(distMin, dist(pointsMerged.get(i), pointsMerged.get(j)));
			}
			return distMin;
		}
	}
	
	public static void merge(ArrayList<Point> points,  ArrayList<Point> pointsMerged){
		int i = 0, j = 0;
		 ArrayList<Point> aux = new  ArrayList<Point>();
		 while(i < points.size() && j < pointsMerged.size()){
			 if(points.get(i).compareTo(pointsMerged.get(j)) < 0)
				 aux.add(points.get(i ++));
			 else 
				 aux.add(pointsMerged.get(j ++));
		 }
		 while(i < points.size())
			 aux.add(points.get(i ++));
		 while(j < pointsMerged.size())
			 aux.add(pointsMerged.get(j ++));
		 
		 pointsMerged = (ArrayList<Point>)aux.clone();
			 
	}
	public static void main(String[] args) {
		
		Scanner sc = null;
		int n = 0;
		
		try{
			sc = new Scanner(new File("cmap.in"));
			n = sc.nextInt();
			for(int i = 0; i < n; i ++){
				int a = sc.nextInt();
				int b = sc.nextInt();
				points.add(new Point(a,b));
			}
		}catch(Exception ex){
			ex.printStackTrace();
		}
		finally{
			sc.close();
		}
		
		Collections.sort(points, new Comparator<Point>(){
			public int compare(Point A, Point B){
				return A.x - B.x;
			}	
		});
		
		//System.out.println(getShortestDistance(0,n - 1));
		
		try{
			PrintWriter writer = new PrintWriter("date.out", "UTF-8");
			writer.println(getShortestDistance(0,n - 1));
		}catch(FileNotFoundException | UnsupportedEncodingException  ex){
			ex.printStackTrace();
		}
		
		
	}

}