Cod sursa(job #1817569)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 28 noiembrie 2016 01:23:28
Problema Cele mai apropiate puncte din plan Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 2.15 kb
import java.io.*;
import java.util.*;


public class Class4{
 
 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
		}
   }
}