PROBLEM LINK:
Author: Rupesh Maity
Tester: Asim Krishna Prasad
Editorialist: Rupesh Maity
DIFFICULTY:
Medium
PREREQUISITES:
DFS, Point in Polygon
PROBLEM:
Given N circles and a point in 2D plane. Check if the point is completely surrounded by circles or not, i.e., if there is a way out.
QUICK EXPLANATION:
Check if the point (x, y) lies inside any of the given circles, then he is trapped. Join the centres of the circles which intersect and consider them as edges. We now have a graph. The point (x, y) is considered trapped only if it lies inside any of the cycles in this graph formed. Find a ray passing through the point (x,y) and not passing thourgh any of the vertices of the graph. Assign the value 1 to all the edges that intersect this ray and 0 to all the other edges. If there are any odd cycles in the graph, the answer is “YES”.
EXPLANATION:
Check if the point (x,y) lies inside any of the given cirlces and print “NO” if it does. Notice that, we cannot pass between two circles if they are intersecting. Thus, we can construct an edge between the centres of these 2 circles representing that you cannot pass through this edge. We check this for every pair of circles given in our input. This can be done in O(N^2), where N is the number of circles. After we’re done constructing all the edges, we now have a graph. The problem now comes down to finding if the given point lies inside any of the cycles formed by this graph.
Now let’s only concentrate on the graph and the point. We know that, if a point lies inside a polygon, all the rays emerging from this point intersect the polygon exactly odd number of times. Using this property of a “Point in a polygon”, we try to find a ray (a line emerging from point (x, y)) which does not pass through any of the vertices of our graph. We are doing this because we want to avoid any complex case that may arise due to the ray passing through a vertex. We need to find a point (x1, y1), such that a ray starting at (x, y) and passing through (x1, y1) does not pass through any of the vertices. One way to do it is by taking (x + 1, 10^5) as (x1, y1). This is because, no vertex in input can lie on the line (x, y) and (x + 1, 10^5), as (xi, yi <= 10^4). I did it differently by fixing x1 = x + 1 and iterating over a few values of y1 until I found a point satisfying my condition.
Now, lets mark all the edges passing through this ray as weight 1 and the rest of the edges as weight 0. Now the problem comes down to finding any cycle in the graph which has odd weight. This can be done by a simple DFS, keeping note of the total weight encountered until now and checking for any odd weighted cycles in the traversal.
Time Complexity: O(N^2)
Author’s Solution:
Author’s solution can be found here.