SNSS2020 R5

Revision ru2, by SendThemToHell, 2020-09-11 16:02:46

Today I have discovered a strange fact about problem D from SNSS round 5.

I believe, most of the accepted solutions were something like "do ternary search over the angle/x-coordinate". It was somewhat hard for me to squeeze it into TL, so I had to do only 20 iterations to get accepted. Today I decided to find out, what is the minimum number of iterations of ternary search required to get AC. Turned out that this number is equal to... 0. The code which gives AC is listed below.

Spoiler

I believe that this code takes the intersection of the bisector of AB and the circle as optimum, which is definitely wrong. Am I missing something?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English SendThemToHell 2020-09-11 16:23:04 8257 Initial revision for English translation
ru3 Russian SendThemToHell 2020-09-11 16:05:46 35
ru2 Russian SendThemToHell 2020-09-11 16:02:46 14 Мелкая правка: 'und 5.\n\nMost of the' -> 'und 5.\n\nI believe, most of the'
ru1 Russian SendThemToHell 2020-09-11 16:02:21 8210 Первая редакция (опубликовано)