First of all, note that since Michael moves faster than all of the squirrels, a solution is guaranteed to exist (and hence some optimal solution exists).

Subtask 1

In this subtask, all squirrels remain on the x-axis during the game of tag. The "intended" greedy solution involves trying to catch all the squirrels to the left of the origin before all the squirrels to the right, and vice versa, but sadly I cannot prove its correctness (with the exception of proof by AC).

Time Complexity: ~\mathcal{O}(N)~

Remark: For the next two subtasks, note that any optimal solution will involve catching the ~N~ squirrels in some order. There can be several such orders, but no matter what, Michael will inevitably have to catch the squirrels in some order.

Now let's convince ourselves that an optimal solution is always found if Michael catches each squirrel as quickly as possible before the next squirrel in this order. Let an optimal solution be such that Michael catches the squirrels in the order ~(s_1,s_2,\dots,s_n)~ and catches each squirrel at the respective point ~((x_1,y_1), (x_2,y_2), \dots, (x_n,y_n))~ at times ~(t_1,t_2,\dots,t_n)~. Now suppose that in this optimal solution, Michael is capable of catching some squirrel ~s_i~ at some time ~T < t_i~, and he can catch it at the point ~(x,y)~. Then, since Michael runs faster than all the squirrels, he can run to ~(x_i,y_i)~ before ~t_i~ (since ~s_i~, on its normal course, would be there at ~t_i~), and we see that a solution in which Michael catches each squirrel as soon as possible is at least as good as this optimal solution, and thus must be optimal itself.

Subtask 2

For subtask 2, with constraints ~1 \le N \le 8~, we have bounds small enough to permit checking every possible order: all ~N!~ of them. Then, it only remains to find how much time it takes to travel from squirrel to squirrel, which can be done via intermediate math or binary search, left as an exercise.

Time Complexity: ~\mathcal{O}(N \cdot N!)~ or ~\mathcal{O}(N \cdot N! \cdot \log(10^{15}))~ ^[1]

Subtask 3

Subtask 3 was simply the improvement from factorial to exponential time, the well-known travelling salesman problem. The most popular solution is to represent each state as a pair of the most recently tagged squirrel and a bitmask representing which squirrels have been previously tagged. Constraints were made to permit binary search to pass (since this isn't a math competition, after all).

Time Complexity: ~\mathcal{O}(N^2 \cdot 2^N)~ or ~\mathcal{O}(N^2 \cdot 2^N \cdot \log(10^{15}))~ ^[1]

^[1] Note that ~\log(10^{15})~ is slightly misleading since you'll be binary searching decimal numbers, so you'll require somewhat more iterations to achieve the required precision, but it's a fair ballpark.