Cod sursa(job #1817433)

Utilizator foobarAlex B. foobar Data 27 noiembrie 2016 20:14:24
Problema Cele mai apropiate puncte din plan Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 4.85 kb
import com.sun.istack.internal.Nullable;

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
import com.sun.istack.internal.Nullable;
import sun.plugin.javascript.navig.Array;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

/**
 * Created by balex on 27.11.2016.
 */
public class Infoarena{
    public static void main(String[] args) throws Exception{
        Map map = new Map("cmap.in");
        PrintWriter out = new PrintWriter("cmap.out");
        out.print(map.cmap());
        out.flush();
        System.out.print(map.cmap());
    }
}
class Coordinate {
    private int x, y;
    public Coordinate(int x, int y){
        this.x = x;
        this.y = y;
    }
    public int getX(){
        return x;
    }
    public int getY(){
        return y;
    }
    public static double distance(Coordinate c1, Coordinate c2){
        return Math.sqrt(Math.pow((c1.x-c2.x),2)+(Math.pow((c1.y-c2.y),2)));
    }
    public boolean hasXBetween(double leftBound, double rightBound){
        return (this.x>leftBound && this.x<rightBound);
    }
}


class Map {
    private Coordinate[] coordsSortedByX;
    private Coordinate[] coordsSortedByY;
    private int coordinatesNo;
    ////
    Map(String fileName){
        try{
            Coordinate[] coordinates;
            Scanner in = new Scanner(new File(fileName));
            coordinatesNo = in.nextInt();
            coordinates = new Coordinate[coordinatesNo];
            for(int i=0;i<coordinatesNo;i++){
                coordinates[i] = new Coordinate(in.nextInt(),in.nextInt());
            }
            coordsSortedByX = sortByX(coordinates);
            coordsSortedByY = sortByY(coordinates);
        }catch (FileNotFoundException e){System.out.println("Error");}
    }

    private Coordinate[] sortByX(Coordinate[] coordinates)  {
        Arrays.sort(coordinates, new Comparator<Coordinate>() {
            @Override
            public int compare(Coordinate c1, Coordinate c2) {
                if(c1.getX() == c2.getX())
                    return 0;
                return c1.getX() < c2.getX() ? -1 : 1;
            }
        });

        return coordinates;
    }

    private Coordinate[] sortByY(Coordinate[] coordinates)  {
        Arrays.sort(coordinates, new Comparator<Coordinate>() {
            @Override
            public int compare(Coordinate c1, Coordinate c2) {
                if(c1.getY() == c2.getY())
                    return 0;
                return c1.getY() < c2.getY() ? -1 : 1;
            }
        });

        return coordinates;
    }

    public double cmap(){
        return leastDistanceWithin(0,coordinatesNo-1);
    }

    private double leastDistanceWithin(int leftmostIndex, int rightmostIndex){  //O(nlogn)
        if(leftmostIndex==rightmostIndex-1)
            return Coordinate.distance(coordsSortedByX[leftmostIndex],coordsSortedByX[rightmostIndex]);
        else {
            double d1 = leastDistanceWithin(leftmostIndex, (leftmostIndex + rightmostIndex) / 2); //O(nlogn)
            double d2 = leastDistanceWithin((leftmostIndex + rightmostIndex) / 2, rightmostIndex); //O(nlogn)
            double δ = Math.min(d1, d2);
            return Math.min(δ, leastDistanceAcross(δ, leftmostIndex, rightmostIndex));//O(n)
        }
    }

    private double leastDistanceAcross(double borderSize, int leftmostIndex, int rightmostIndex){       //O(n)
        double leastDistanceAcross = Double.MAX_VALUE;
        ArrayList<Coordinate> coordsWithinBorder = filterCoordsWithinBorder((leftmostIndex+rightmostIndex)/2,borderSize);     //O(n)

        if(coordsWithinBorder != null)
            for(int i=0;i<coordsWithinBorder.size()-1;i++){
                for(int j=i+1;j<=Math.min(i+7,coordsWithinBorder.size()-1);j++){
                    if(Coordinate.distance(coordsSortedByX[i],coordsSortedByX[j])<leastDistanceAcross)
                        leastDistanceAcross = Coordinate.distance(coordsSortedByX[i],coordsSortedByX[j]);
                }
            }

        return leastDistanceAcross;
    }

    @Nullable
    private ArrayList<Coordinate> filterCoordsWithinBorder(int medianIndex, double borderSize) {      //O(n)
        ArrayList<Coordinate> coordsWithinBorder = new ArrayList<>();
        double borderLeftBound = coordsSortedByX[medianIndex].getX()-borderSize;
        double borderRightBound = coordsSortedByX[medianIndex].getX()+borderSize;

        for(Coordinate c : coordsSortedByY){   //O(n)
            if(c.hasXBetween(borderLeftBound,borderRightBound))
                coordsWithinBorder.add(c);
        }

        return coordsWithinBorder.isEmpty()? null : coordsWithinBorder;
    }

}