BaoBao is lost on an infinite two-dimensional plane!Starting from,BaoBao has to find his way to his house located at,But this is not an easy task for him, as there arenround obstacles scattering on the plane. The center of thei-th obstacle, whose radius isriis located at ,BaoBao is free to move on the plane, but his route can not intersect with any obstacle. We say BaoBao has successfully arrived at his house, if and only if the distance between the final position of BaoBao andis not greater than R,and the segment connecting the final position of BaoBao anddoes not intersect with any obstacle. BaoBao is eager to go home, so your task is to help BaoBao find the shortest route which starts fromand leads to his successful arrival to his house.
BaoBao is lost on an infinite two-dimensional plane! Starting from(ax,ay), BaoBao has to find his way to his house located at (bx,by), But this is not an easy task for him, as there are n round obstacles scattering on the plane. The center of the i-th obstacle, whose radius is ri is located at (xi,yi) ,BaoBao is free to move on the plane, but his route can not intersect with (but can be tangent to) any obstacle. We say BaoBao has successfully arrived at his house, if and only if the distance between the final position of BaoBao and (bx,by) is not greater than R, and the segment connecting the final position of BaoBao and (bx,by) does not intersect with (but can be tangent to) any obstacle. BaoBao is eager to go home, so your task is to help BaoBao find the shortest route which starts from (ax,ay)and leads to his successful arrival to his house.
