Cod sursa(job #1816461)

Utilizator mike406Mike Mike mike406 Data 26 noiembrie 2016 15:24:12
Problema Cele mai apropiate puncte din plan Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 5.8 kb
/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package pb4;

import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedHashMap;
import java.util.Scanner;
import javafx.util.Pair;

/**
 *
 * @author Mihai
 */
 class Pb4 {
    
    static LinkedHashMap<Pair<Integer,Integer>,Integer> x;
    
    static LinkedHashMap<Pair<Integer,Integer>,Integer> intersectie(LinkedHashMap<Pair<Integer,Integer>,Integer> y, LinkedHashMap<Pair<Integer,Integer>,Integer> x,int st,int dr,int first,double d) {
        LinkedHashMap<Pair<Integer,Integer>,Integer> rez = new LinkedHashMap<>();
        int mij = (st+dr)/2;
        Pair<Integer,Integer> pair = (new ArrayList<>(x.keySet())).get(mij);
        
        int nr = 0;
        if(first == 1) {
            ArrayList<Pair<Integer,Integer>> y1 = new ArrayList<>(y.keySet());
            for(int i=0;i<y1.size();i++) {
                if(y1.get(i).getKey()<=pair.getKey()) {
                    nr++;
                    rez.put(y1.get(i),nr);
                }
            }
        }
        else if(first == 0) {
            ArrayList<Pair<Integer,Integer>> y1 = new ArrayList<>(y.keySet());
            for(int i=0;i<y1.size();i++) {
                if(y1.get(i).getKey()>pair.getKey()) {
                    nr++;
                    rez.put(y1.get(i),nr);
                }
            }
        }
        else {
            ArrayList<Pair<Integer,Integer>> y1 = new ArrayList<>(y.keySet());
            for(int i=0;i<y1.size();i++) {
                if(Math.abs(y1.get(i).getKey() - pair.getKey()) <= d) {
                    nr++;
                    rez.put(y1.get(i),nr);
                }
            }
        }
        return rez;
    }
    
    static double minPerechi(LinkedHashMap<Pair<Integer,Integer>,Integer> y) {
        
        ArrayList<Pair<Integer,Integer>> y1 = new ArrayList<>(y.keySet());
        double min = distanta(y1.get(0),y1.get(1));
        
        for(int i=0;i<y1.size()-1;i++)
            for(int j=i+1;j<y1.size();j++) {
                double d = distanta(y1.get(i),y1.get(j));
                if(d < min)
                    min = d;
            }
        return min;
    }
    
    static double distanta(Pair<Integer,Integer> a,Pair<Integer,Integer> b) {
        return Math.sqrt((a.getKey()-b.getKey())*(a.getKey()-b.getKey()) + (a.getValue()-b.getValue())*(a.getValue()-b.getValue()));
    }
    
    static double calcD3(LinkedHashMap<Pair<Integer,Integer>,Integer> y) {
        
        ArrayList<Pair<Integer,Integer>> y1 = new ArrayList<>(y.keySet());
        double min = distanta(y1.get(0),y1.get(1));
        
        for(int i=0;i<y1.size()-1;i++) {
            for(int j=i+1;j<y1.size();j++) {
                double d = distanta(y1.get(i),y1.get(j));
                if(d < min)
                    min = d;
            }
        }
        return min;
    }
    
    static double DivImp(int st,int dr,LinkedHashMap<Pair<Integer,Integer>,Integer> y) {
        double d;
        if(y.size()<4)
            d = minPerechi(y);
        else {
            int mij = (st+dr)/2;
            LinkedHashMap<Pair<Integer,Integer>,Integer> SY = intersectie(y,x,st,dr,1,0);
            LinkedHashMap<Pair<Integer,Integer>,Integer> DY = intersectie(y,x,st,dr,0,0);
            double d1 = DivImp(st,mij,SY);
            double d2 = DivImp(mij+1,dr,DY);
            d = Math.min(d1,d2);
            LinkedHashMap<Pair<Integer,Integer>,Integer> LY = intersectie(y,x,st,dr,2,d);
            double d3 = calcD3(LY);
            d = Math.min(d, d3);
        }
        return d;
    }

    public static void main(String[] args) {
        
        try {
            Scanner sc = new Scanner(new File("date.in"));
            LinkedHashMap<Pair<Integer,Integer>,Integer> y = new LinkedHashMap<>();
            x = new LinkedHashMap<>();
            
            int n = sc.nextInt();
            for(int i=1;i<=n;i++)
                x.put(new Pair(sc.nextInt(),sc.nextInt()), i);
            
            ArrayList<Pair<Integer,Integer>> temp = new ArrayList<>(x.keySet());
            
            Comparator<Pair<Integer,Integer>> c = new Comparator<Pair<Integer,Integer>>() {
                @Override
                public int compare(Pair<Integer, Integer> o1, Pair<Integer, Integer> o2) {
                    return o1.getKey()-o2.getKey();
                }
            };
            Collections.sort(temp,c);
            x.clear();
            for(int i=0;i<temp.size();i++)
                x.put(new Pair(temp.get(i).getKey(),temp.get(i).getValue()),i);
            
            temp.clear();
            temp = new ArrayList<>(x.keySet());
            Collections.sort(temp,new Comparator<Pair<Integer,Integer>>() {
                @Override
                public int compare(Pair<Integer, Integer> o1, Pair<Integer, Integer> o2) {
                    return o1.getValue()-o2.getValue();
                }
            });
            for(int i=0;i<temp.size();i++)
                y.put(new Pair(temp.get(i).getKey(),temp.get(i).getValue()),i);
            
            double d = DivImp(0,n-1,y);
            System.out.println(d + " proba");
            
            FileWriter out = new FileWriter(new File("date.out"));
            out.write(d+"");
            out.close();
            
        } catch (FileNotFoundException ex) {
            System.out.println(ex.toString());
        } catch (IOException ex) {
            System.out.println(ex.toString());
        }
    }
    
}