aryam_agarwal's blog

By aryam_agarwal, history, 3 months ago, In English

I was recently attempting a problem titled Path finder and had hit a roadblock. I would really appreciate if you can suggest your approach to the problem. Below is a rough outline of what I remember from the problem statement. Problem statement- You are given a point P(x,y) and a set of n circles. You have to find if there exists a path from origin(0,0) to P without crossing any of the circles (you can not touch the circle as well). The path must be only entirely within first quadrant Q NOTE: There will be no case where the circles form a train of circles enclosing the point among themselves. You can also assume that the point is to the right and above all circles if none of the circles contain the point.

Input: n: The number of circles. For each circle: three values (c_x, c_y, r) representing the center coordinates and the radius. Two values x and y representing the coordinates of point P.

Output: Print “YES” if a path exists; otherwise, print “NO”.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it 2002C - Black Circles, if yes you can read the editorial

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No it’s not this problem. Circles are not increasing in size they have constant dimensions.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      sorry, i just thought that this is similar

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

find the distances between the center of the circles and the point P, also find the distance of the origin with the point P, you will find the answer