SendThemToHell's blog

By SendThemToHell, history, 4 years ago, translation, In English

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?

Full text and comments »

  • Vote: I like it
  • +30
  • Vote: I do not like it