CareerCup

It looks like the question is directly copy pasted from Stackoverflow: h t tp:// stackoverflow. com/questions/14994179/given-a-circle-with-n-defined-points-and-a-point-m-outside-the-circle-find-the

How the defined points stored? Are they clockwise or randomly stored? If it is randomly, I guess it's impossible to do this in O(logn) time. If it is clockwise of anticlockwise, this is a binary search problem.

What about this:
(1)Get the line defined by the circle center O and the outside point P, then we can get the diameter AOB on this line. Let's say the endpoint close to P is A, and the other is B.
(2)Now all the N given points are in the circle defined by center P and radius PB, while no point is in the circle defined by center P and radius PA.
(3)Binary search radius till we find a radius R with which the defined circle has only one given point.

Join the line from center of circle to the outside point. Now the point at minimum distance from M has the least angle with this line i.e. min(theta, 360 - theta) should be the least among all the points.
If we assume points are in order clockwise/anti clockwise this breaks down to the problem of rotated array which is solvable in log(N)

Here's a verbal description of a logarithmic algorithm:

Let C be the center of the circle and let P be the point of intersection of the circle with the line segment joining C and M. Let N_i designate the ith point in the list of N points ordered counter-clockwise (we must assume they are given to us in an ordering like this), and let -pi <= A_i < pi be the the *signed* measure of the angle from P to N_i. Then the problem is reduced to finding the index i so that |A_i| is minimized.

Note that the list [ |A_1|, |A_2|, ..., |A_N| ] is cyclically sorted, i.e., it is either ascending and then descending or else it is descending and then ascending. We want to find the minimum element. This can be achieved in logarithmic time via a modification of binary search.

Assuming the points are in order

public static Point findClosest(final Point m, final List<Point> circlePoints)
    {
        int index = Collections.binarySearch(circlePoints, m, new Comparator<Point>() {
            @Override
            public int compare(Point o1, Point o2)
            {  
                int idx = circlePoints.indexOf(o1);
                double dist,distLeft, distRight;
                    dist = findDistance(o2, o1);
                if(idx-1>0)
                {
                    distLeft = findDistance(o2, circlePoints.get(idx-1));
                    if(distLeft<dist)
                        return 1;
                }
                if(idx+1<circlePoints.size())
                {
                    distRight = findDistance(o2, circlePoints.get(idx+1));
                    if(distRight<dist)
                        return -1;
                }
                return 0;
            }
            
        });
       return circlePoints.get(index);
    }


    public static Double findDistance(Point p1, Point p2)
    {
        if(p1==null || p2==null)
            return 0d;
        return Math.sqrt(Math.pow(p1.x-p2.x, 2)+Math.pow(p1.y-p2.y, 2)); 
    }



static class Point
    {
        Float x;
        Float y;
        public Point(float x, float y)
        {
            this.x = x;
            this.y = y;
        }
}

Idea: binary search for the smallest value
Use distance directly.
Compute three values for the middle point:
(1) if go down, choose the right half
(2) if go up, choose the left half
(3) if valley, return the answer

the question that makes sense to me is that setup is given with a circle and N points.
Then multiple queries are made with different points outside the above circle. Each query should return closet point from N point set.

I guess, we can modify the closest pair of points algorithm of complexity O(n logn) to run in (log n).