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).