What is the minimum distance Runu needs to walk?

Revision en6, by ovis96, 2018-06-08 00:21:54

Given n circles in 2D coordinate system (their centers and radius, circles can overlap). You are also given the position of Runu. What is the minimum distance she needs to walk to get out of all the circles. More formally, if Runu's position is P and there is a point Q such that Q is out of every n circles, you have to minimize the euclidian distance of Pand Q for all such Q's .

This problem is out of judges, came to my mind. Can you provide me a solution? What is the tight bound of n then? If anyone had seen problem like this before or thought something like this, please do share.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en7 English ovis96 2018-06-08 00:27:23 1 Tiny change: '* of **P**and **Q** ' -> '* of **P** and **Q** '
en6 English ovis96 2018-06-08 00:21:54 0 Tiny change: ' my mind. What is t' -> ' my mind. Can you provide me a solution? What is t' (published)
en5 English ovis96 2018-06-08 00:20:45 31 Tiny change: ' my mind. What is t' -> ' my mind. Can you provide me a solution? What is t'
en4 English ovis96 2018-06-08 00:18:46 52 Tiny change: 'ther than n^3?\nIf a' -> 'ther than $n^3?\nIf a'
en3 English ovis96 2018-06-08 00:12:44 4 Tiny change: '* of **P**, **Q** for' -> '* of **P**and **Q** for'
en2 English ovis96 2018-06-08 00:11:36 40
en1 English ovis96 2018-06-08 00:10:32 623 Initial revision (saved to drafts)