Cracow Sights#405

Cracow Sights (Editorial)

Author:

Pavlo Tsitsei

Task preparation:

Pavlo Tsitsei

Editorial:

Pavlo Tsitsei

Block : x_i^2+y_i^2\le 18 for all :

We can change from to if x^2+y^2=a^2+b^2, which means that we can change from (-x, y) to or from to , so we can make all coordinates in the input of type 0\le x\le y and group them together. In this way, we have 10 types of such groups (if we don't count ). So we can solve it as the third block.

Block : n=1:

Note that the distance from to is \sqrt{x^2+y^2}, so if we change to where x^2+y^2=a^2+b^2, then the distance doesn't change. So, the minimum distance is from to the point in the input and from this point to .

Block : n\le 10:

We can try each permutation of points that defines the path we take, and the first and last elements will be . The total complexity will be .

Block : without additional constraints:

We can change the coordinates of each point from to (0, \sqrt{x^2+y^2}). Then, the answer is the maximum of these points times 2 (since we need to return).