What is the minimum distance Runu needs to walk?

Правка en6, от 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.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en7 Английский ovis96 2018-06-08 00:27:23 1 Tiny change: '* of **P**and **Q** ' -> '* of **P** and **Q** '
en6 Английский 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 Английский 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 Английский ovis96 2018-06-08 00:18:46 52 Tiny change: 'ther than n^3?\nIf a' -> 'ther than $n^3?\nIf a'
en3 Английский ovis96 2018-06-08 00:12:44 4 Tiny change: '* of **P**, **Q** for' -> '* of **P**and **Q** for'
en2 Английский ovis96 2018-06-08 00:11:36 40
en1 Английский ovis96 2018-06-08 00:10:32 623 Initial revision (saved to drafts)