Can someone please explain how to solve this question ?
Given a continuous plane, there are N circles each having coordinate like (cix, ciy) and radius ri. Given a rectangle( the rectangle has length parallel to x-axis and breadth parallel to y-axis) having top-left corner as P1(p1x, p1y) and bottom-right corner as P2(p2x, p2y). Tell if it is possible( 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).
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.
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