SNSS2020 R5

Правка ru3, от SendThemToHell, 2020-09-11 16:05: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?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский SendThemToHell 2020-09-11 16:23:04 8257 Initial revision for English translation
ru3 Русский SendThemToHell 2020-09-11 16:05:46 35
ru2 Русский SendThemToHell 2020-09-11 16:02:46 14 Мелкая правка: 'und 5.\n\nMost of the' -> 'und 5.\n\nI believe, most of the'
ru1 Русский SendThemToHell 2020-09-11 16:02:21 8210 Первая редакция (опубликовано)