Cod sursa(job #2199109)

Utilizator TwoOfDiamondsDaniel Alexandru Radu TwoOfDiamonds Data 26 aprilie 2018 18:01:35
Problema Cele mai apropiate puncte din plan Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 5.27 kb
import java.util.Scanner;
import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
 
class Point
{
    public int x, y;
    public int px, py;
}
 
class DistMin
{
    public static void main(String[] args)
    {
        ArrayList<Point> puncteX = new ArrayList<Point>();
        ArrayList<Point> puncteY = new ArrayList<Point>();
        try
        {
            Scanner sc = new Scanner(new java.io.File("cmap.in"));
             
            int n;
            n = sc.nextInt();
             
            //puncte = new Point[n];
             
            for(int i = 0; i < n; i++)
            {
                Point p = new Point();
                p.x = sc.nextInt();
                p.y = sc.nextInt();
                puncteX.add(p);
                puncteY.add(p);
            }
             
            sc.close();
             
            //apel catre functia de det
            //Collections.sort(puncteX, (Point a, Point b)->
            //{
            //  return a.x - b.x;
            //});
            Collections.sort(puncteX, new Comparator<Point>(){
                public int compare(Point a, Point b){
                    return a.x - b.x;
                }});
            //Collections.sort(puncteY, (Point a, Point b)->
            //{
            //  return a.y - b.y;
            //});
             
            Collections.sort(puncteY, new Comparator<Point>(){
                public int compare(Point a, Point b){
                    return a.y - b.y;
                    }});
             
            for(int i = 0; i < puncteX.size(); i++)
            {
                //puncteX.get(i).py = Collections.binarySearch(puncteY, puncteX.get(i), (Point a, Point b) ->
                //{
                //  return a.y - b.y;
                //});
                puncteX.get(i).py = Collections.binarySearch(puncteY, puncteX.get(i), new Comparator<Point>(){
                    public int compare(Point a, Point b){
                        return a.y-b.y;
                        }});
                puncteY.get(puncteX.get(i).py).px = i;
            }
             
            PrintWriter pw = new PrintWriter(new FileWriter(new File("cmap.out")));
             
            pw.println(dist(puncteX, puncteY , 0, puncteX.size()));
            //for(int i = 0; i < n; i++)
            //{
            //  pw.println(puncte.get(i).x + " " +puncte.get(i).y);
            //}
             
            pw.close();
        }
         
        catch(Exception ex)
        {
            System.out.println("404");
        }
    }
     
    static double getdistance(Point a, Point b)
    {
        double x = a.x - b.x;
        x *= x;
        double y = a.y - b.y;
        y *= y;
        return Math.sqrt(x + y);
    }
     
    static double dist(ArrayList<Point> puncteX, ArrayList<Point> puncteY, int beg, int end)
    {
        if(end - beg < 2)
            return Double.MAX_VALUE;
        if(end - beg <= 3)
        {
            double min;
            double alpha = getdistance(puncteX.get(beg), puncteX.get(beg+1));
            if(end - beg == 3)
            {
                double beta = getdistance(puncteX.get(beg), puncteX.get(beg+2));
                double theta = getdistance(puncteX.get(beg+1), puncteX.get(beg+2));
                min = alpha < beta ? alpha : beta;
                min = theta < min ? theta : min;
            }
            else
                min = alpha;
            return min;
        }
         
        int linie = beg + (end - beg) / 2;
        double d1 = dist(puncteX, puncteY, beg, linie);
        double d2 = dist(puncteX, puncteY, linie, end);
        double min = d1 < d2 ? d1 : d2;
        double d3 = getd3(puncteX, puncteY, beg, end, linie, min);
         
        return d3 < min ? d3 : min;
         
    }
     
    static double getd3(ArrayList<Point> puncteX, ArrayList<Point> puncteY, int beg, int end, int linie, double min)
    {
        ArrayList<Point> banda = new ArrayList<Point>();
        ArrayList<Point> bandaY = new ArrayList<Point>();
        boolean[] shouldadd = new boolean[puncteX.size()];
         
        int pozlinie = puncteX.get(linie).x;
         
        for(int i = beg; i < end; i++)
        {
            shouldadd[puncteX.get(i).py] = false;
            double distLine = puncteX.get(i).x - pozlinie;
            if(distLine < 0)
                distLine *= -1;
            if(distLine <= min)
            {
                banda.add(puncteX.get(i));
                shouldadd[puncteX.get(i).py] = true;
            }
        }
         
        for(int i = 0; i < puncteX.size(); i++)
        {
            if(shouldadd[i])
            {
                bandaY.add(puncteY.get(i));
            }
             
        }
         
        for(int i = 0; i < bandaY.size(); i++)
        {
            int limit = 15 < bandaY.size() - i - 1 ? 15 : bandaY.size() - i - 1;
             
            for(int j = 1; j <= limit; j++)
            {
                double dist = getdistance(bandaY.get(i), bandaY.get(i+j));
                if(dist < min)
                {
                    min = dist;
                }
            }
             
        }
         
        return min;
    }
}