Circles and path


  • 0
    P

    You have a path which is from -inf to +inf in x-axis and 0 to 1 in y-axis. You are given a list of position of circles and their radiuses. Output whether you can go through this path, or to say whether some circles form a full obstacle to vertically hide the road.

    path:

    y =1 ------------------------
    y = 0 -------------------------

    class Circle:
        def __init__(self, x, y, r):
            self.x = x
            self.y = y
            self.radius = r
    

  • 0
    V

    Taking a stab at this- Sort the given list of position of circles by x (and by y, if x is same). Maintain the minY and maxY for contiguous overlapping/touching circles. Reset the minY and maxY values to current circle's values when you encounter a circle that doesn't overlap with the previous one.

    Return if anytime maxY - minY >= 1. Also, minY should never be < 0.

    --

    Edit: This solution won't work for cases where a circle appears after the contiguous cluster of circles and that intersects with some previous cluster. Therefore, all previous circles will need to be tested for intersection.

    Old Code (Java)-

    private static boolean doesPathExist(ArrayList<Circle> list)
    {
    	Collections.sort(list, new Comparator<Circle>()
    	{
    		public int compare(Circle c1, Circle c2)
    		{
    			if (c1.x == c2.x)
    			{
    				return (c1.y - c2.y) < 0 ? -1 : (c1.y - c2.y == 0) ? 0 : 1;
    			}
    			else
    			{
    				return (c1.x - c2.x) < 0 ? -1 : (c1.x - c2.x == 0) ? 0 : 1;
    			}
    		}
    	});
    	
    	Circle first = list.get(0);
    	double minY = Math.max(0, (first.y - first.radius));
    	double maxY = first.y + first.radius;
    	
    	for (int i=1; i<list.size(); i++)
    	{
    		if (maxY - minY >= 1)
    		{
    			return false;
    		}
    		
    		double curY = list.get(i).y;
    		double curRad = list.get(i).radius;
    		
    		if (overlaps(list.get(i), list.get(i-1)))
    		{
    			minY = Math.max(0, Math.min(minY, curY - curRad));
    			maxY = Math.max(maxY, curY + curRad);
    		}
    		else
    		{
    			minY = Math.max(0, curY - curRad);
    			maxY = curY + curRad;
    		}
    	}
    	
    	return (maxY - minY) < 1;
    }
    	
    private static boolean overlaps(Circle c1, Circle> c2)
    {
    	double x = Math.abs(c1.x - c2.x);
    	double y = Math.abs(c1.y - c2.y);
    	
    	return (Math.sqrt(x*x + y*y) - c1.radius - c2.radius) <= 0;
    }
    

    	ArrayList<Circle> list = new ArrayList<Circle>();
    	list.add(new Circle(0.5, 0.2, 0.5));
    	list.add(new Circle(0.7, 0, 0.2));
    	list.add(new Circle(0.9, 0.3, 0.5));
    	list.add(new Circle(1.5, -1, 1));
    	list.add(new Circle(2, -0.1, 1));
    	
    	System.out.println(doesPathExist(list)); // output: true

  • 0
    P

    @vishalhemnani Won't work for some test cases. Check right answer here.
    https://reeestart.wordpress.com/2016/07/02/google-find-a-path-among-circles/


  • 0
    V

    @pushazhiniao Right, there could be a circle that appears after the cluster and still intersects with a previous cluster.
    So, all previous circles will need to be checked for intersection.
    Unfortunately that would degrade the complexity to O(n2). :(

    Any more efficient solution to this problem?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.