# Circles and path

• 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
``````

• 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;

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);
}
}

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);

}
``````

``````	ArrayList<Circle> list = new ArrayList<Circle>();

System.out.println(doesPathExist(list)); // output: true``````

• @vishalhemnani Won't work for some test cases. Check right answer here.