Can someone please explain how to solve this question ?

Given a continuous plane, there are **N** circles each having coordinate like **(c _{i}x, c_{i}y)** and radius

**r**. Given a rectangle( the rectangle has length parallel to x-axis and breadth parallel to y-axis) having top-left corner as

_{i}**P1(p**and bottom-right corner as

_{1}x, p_{1}y)**P2(p**. Tell if it is possible(

_{2}x, p_{2}y)**true or false**) to travel from

**P1**to

**P2**

**without touching or crossing the circles while being inside the rectangle.**

**NOTES:**

**The coordinates are NOT necessarily integer coordinates.****The trajectory of travel from P1 to P2 may not necessarily be a straight line, it can be anything (think of it like a river).**

Auto comment: topic has been updated by ex_hausted (previous revision, new revision, compare).Give us a link to the problem, and/or ranges for coordinates, i might have a way to solve this, or at least help you a little bit.

Sorry, this was an interview problem, don't have a link. Also, coordinates can be anything that can be solved in general, no special coordinates.

Im really sorry then, but this is full of questions for ongoing interviews. Can't help you.

I think you are referring to this task on interviewbit. It can be solved using BFS.

The question in this post doesn't necessarily have integer coordinates, it is a continuous plane. Also, the interviewbit question assumes integer coordinates, have defined directions(8 directions) to travel to, here the trajectory of travel from P1 to P2 can be anything.

Almost the same task.

This is a very interesting problem. I believe I know of a solution, but it depends on how large the constraint for N is. This solution should run O(N^2). First we build a graph on the circles, there is an edge between two circles if they intersect (the distance between their centers is no more than the sum of their radii). Now we perform BFS/DFS on the circles. If we are able to connect the top of the rectangle to the bottom of the rectangle or top to left or left to right or bottom to right, then the answer should be false. Otherwise the answer is true.

I had the same solution in mind but do you know if there's any divide-and-conquer/line-sweep trick to bring it down from N^2?

Normally, I would try something like that, but it seems quite difficult (maybe even impossible) in this case because of two issues:

That being said, there may be ways to optimize my naive BFS/DFS approach since a lot of the N^2 edges will be redundant.

Its simple disjoint set union, merge Circle or just those points basically which interset that can be possible hindrance to path, if there is hindrance then it is not possible else it's possible,

Hindrance is of the form top-right, top-bottom, bottom-right, bottom left

Total complexity will be O(N^2) (also O(N log N) using Delaunay triangulation not needed tho) as you can merge in incremental order to skip, parent merging.

This is based on the assumption that when circle intersect projection of those diameter will block the whole path