import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class NearesPoint {

    List<Double> latList;

    List<Double> lonList;

    List<Point> pointList;

    public NearesPoint(){
        Collections.sort(pointList);
    }


    /**
     * Find nearest point from the given point p
     * @param p
     * @return
     */
    public Point findNearest(Point p){

        //Find nearest point in List using lat
        int pivot = Collections.binarySearch(pointList,p);

        Point p1 = nearest(0,pivot,p);
        Point p2 = nearest(pivot+1,pointList.size()-1,p);

        if(p1==null && p2!=null){
            return p2;
        }
        if(p2==null && p1!=null){
            return p1;
        }

        Point res = new Point(); //Find p1 or p2 which is nearest to p
        return res;



    }

    private Point nearest(int low, int high, Point p){
        if(low>high){
            return null;
        }
        if(low ==high){
            return pointList.get(low);
        }

        int m = (low+high)/2;

        Point p1 = nearest(low,m,p);
        Point p2 = nearest(m+1,high,p);

        if(p1==null && p2!=null){
            return p2;
        }
        if(p2==null && p1!=null){
            return p1;
        }

        Point res = new Point(); //Find p1 or p2 which is nearest to p
        return res;
    }


    static class Point implements Comparable<Point>{
        Double lat;
        Double lon;

        @Override
        public int compareTo(Point o) {
            //Points are sorted based on latitude, if lats are equal than based on lon
            int d =  this.lat.compareTo(o.lat);
            if(d==0){
                return this.lon.compareTo(o.lon);
            }
            return d;
        }
    }
}