Cod sursa(job #1282047)

Utilizator veruxyTeste G veruxy Data 3 decembrie 2014 22:05:18
Problema Cele mai apropiate puncte din plan Scor 60
Compilator java Status done
Runda Arhiva educationala Marime 3.8 kb
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
  
class Main {
  
    static int nrPuncte;
    static Punct[] array ;
    static Punct[] copyOfSortedArray ;
    static Punct[] aux ;
      
    static long dist(Punct A, Punct B){
        long x= B.x - A.x,y=B.y - A.y;
        return x*x+y*y;
    }
      
    static void merge( int st, int dr ){
          
        int mid = (st + dr) / 2, p1 = st, p2 = mid + 1, len = 0;
           
        while (p1 <= mid && p2 <= dr)
            if (array[p1].x < array[p2].x)
                aux[++len] = array[p1++];
            else
                aux[++len] = array[p2++];
        while (p1 <= mid)
               aux[++len] = array[p1++];
        while (p2 <= dr)
               aux[++len] = array[p2++];  
                 
        System.arraycopy(aux,1,array,st,dr-st+1);           
       // for (int i = st, j = 1; i <= dr; ++i, ++j)
          //  array[i] = aux[j];
    }
      
    static long divide(int st, int dr){
          
        long res = Long.MAX_VALUE;
        if (dr - st <= 2) {
            for (int i = st; i <dr; ++i)
                for (int j = i + 1; j <= dr; ++j)
                    res = Math.min(res, dist(array[i], array[j]));
            Arrays.sort(array, st, dr+1);
            return res;
        }
           
        int mid = (st + dr) / 2;
        res = Math.min(divide(st, mid), divide(mid + 1, dr));
           
        merge(st, dr);
           
        int len = 0;
        for (int i = st; i <= dr; ++i)
            if (Math.abs(array[i].x - copyOfSortedArray[mid].x) < res) //nu<=
                aux[++len] = array[i];
        int t=len-7;   
        for (int i = 1; i < t; ++i)
            for (int j = i + 1, cnt = 1; cnt <= 7 && j <= len; ++j, ++cnt) //aux.length-mare
                res = Math.min(res, dist(aux[i], aux[j]));
           
        return res;
    }
      
    public static void main(String args[]) throws NumberFormatException, IOException{
  
       BufferedReader br = new BufferedReader(new FileReader("cmap.in"));
       nrPuncte = Integer.valueOf(br.readLine());
       array = new Punct[nrPuncte+1];
       aux = new Punct[nrPuncte+1];
       copyOfSortedArray = new Punct[nrPuncte+1];
       String cline[];
       long x,y;
       for (int index = 1 ; index<=nrPuncte; index++) {
           cline=br.readLine().split(" ");
            x = Integer.parseInt(cline[0]);
            y = Integer.parseInt(cline[1]);
           array[index] = new Punct(x, y);
           //aux[index] = new Punct();
       }
      // br.close();
       Arrays.sort(array,1,nrPuncte, new Comparator<Punct>() {
  
            @Override
            public int compare(Punct o1, Punct o2) {
                if(o1.x < o2.x)
                    return -1;
                if(o1.x > o2.x)
                    return 1;
                return 0;
            }
        });
              
           System.arraycopy(array,1,copyOfSortedArray,1,nrPuncte);
    //    for(int index = 1; index <= nrPuncte;index++ ){
          //  copyOfSortedArray[index] = new Punct(array[index].x, array[index].y);
     //   }
               
        PrintWriter printer = new PrintWriter("cmap.out");
        printer.printf("%.6f\n", Math.sqrt(divide(1, nrPuncte)));
        printer.close();
    }
}
class Punct implements Comparable<Punct>{
    long x,y;
  
    public Punct(long x, long y) {
        this.x = x;
        this.y = y;
    }
  
    public Punct() {
       
    }
  
    @Override
    public int compareTo(Punct o) {
        if(y < o.y)
            return -1;
        if(y > o.y)
            return 1;
        return 0;
    }
}