I solved that problem by using Manhattan distance. So i think this problem is also about Manhattan distance. Anyway, this might not be a good problem...

This is an excellent problem!

The only solution I can think of requires solving an LP with 2ⁿ variables. The idea is that every embedding can be decomposed into a convex combination of cut metrics.

just open all the modulo write 8 formulas and we want max among them.So find max of all formulas for each of 8 possibilities.

Alright, I'll try to explain my code. Hopefully I won't miss anything important.

The first case is when we don't need to use the subway at all. We can check this separately.

The second case is when some dwarf will use the subway. To solve it, let's find the closest station for each dwarf and then sort dwarves in the decreasing order of this distance. This part is quite standart so I'll skip its explanation.

Now, let's replace our coordinate system with the following substitution: (x' = x + y, y' = x - y). We'll use it later.

Obviously, if some dwarf uses the subway, then all dwarves with smaller distance to the closest subway station will also use the subway. Let's do a binary search over the answer. Now we need to find such K that the first K dwarves will walk to the meeting point and the rest N - K dwarves will use the subway and then walk to the meeting point. If such value of K exists, then we need to move the right bound in our binary search, otherwise we need to move the left bound.

Suppose we want to check whether the answer is  ≤ X. Remember that we replaced the original coordinate system with the new one. In this new coordinate system each dwarf can walk to every point of the square with side 2X centered at its original location. It means that if we fix some K and ask the first K dwarves to walk to some point then this point should lie in the intersection of all described squares for these dwarves. The intersection of several squares is obviously a rectangle. So now for the fixed K we need to check whether the rest N - K dwarves can reach this rectangle using the subway. Obviously it's enough to check only the K + 1-th dwarf since all other dwarves will reach the closest subway station at least as fast as the K + 1-th one. Suppose it takes t seconds for the K + 1-th dwarf to reach the subway station. It means that he will have X - t seconds to get to our rectangle after getting out of the subway. Thus we can simply extend our rectangle by X - t units in each direction and check whether there's a subway station inside it.

Now we have the following problem: given many rectangles we need to check whether there exists at least one rectangle containing the subway station inside it. This can be solved with a simple scan-line algorithm so I'll skip its explanation as well.

The overall complexity is O(Nlog²N).