You are Given N circles on a 2D co-ordinate plane. You are initially standing on the point (X1, Y1) and wish to go to the point (X2, Y2) according to following rules:- — You travel at speed of 1 unit/sec — You incur d damage when you're beyond any of the circular regions for d time. i.e if you spend 0.55 seconds outside the circular region, you suffer from 0.55 damage — The circular regions may overlap
You need to find the minimum damage you can suffer while traveling from starting point to the final point. Answer needs to be truncated to exactly 6 decimal points.
INPUT FORMAT :- The first line contains X1, Y1, X2 and Y2 (The co-ordinates of the starting and end positions) Next line contains integer N, denoting number of circles Each of the next N lines is a 3-tuple wherein the ith line contains Xi, Yi and Ri (the X and Y co-ordinates of the center and the radius of the ith circle)
For instance:- 0 0 2 2
1
1 1 1
One optimal path is to go straight from origin to 2,2. Distance covered outside the circle would be 2 * (sqrt(2) — 1) = 0.828427
interesting indeed
dijkstra comes to mind, but it's too slow right
Maybe it's possible to kinda optimise number of edges in some way.
Eg. have a quick way of checking whether an edge even makes sens (ie. no point for this edge to exist because going through some circle first will always be better).
Mark each circle as a node. Min distance (edge length) between 2 circles is max (0, sqrt(dx^2+dy^2) — r1 — r2). Then you'll also need to handle the edges between the start and end with the nodes in a similar way.
Consider the case when a line segment(edge) between centers of two circles(nodes) passes through a circular region.
The actual distance between the nodes C1 and C2 would he less than sqrt(dx^2 + dy^2) — R1 — R2 We would need to subtract the length P from it(P being the length of the edge that lies inside the circular region. ...Plz suggest a way of implementing that.
I am unable to attach pictures because of Non-positive rating.
Interesting observation. You don't have to bother to correct these because running Dijkstra will take care of that. Let's say nodes A, B, and C are collinear. Naturally the algorithm week go A->B->C and ignore A->C (which is longer).