Subtask 1

First, let's consider the generalization of this problem to any weighted graph ~G~: find the maximum, over all 2-colouring of vertices, of the minimum weight edge between two vertices of the same colour.

Let us define ~G(w)~ to be the subgraph of ~G~ with all edges with weight at most ~w~. If ~G(w)~ is bipartite, then by using the 2-colouring, we know the answer for ~G~ is strictly greater than ~w~. So, the answer is the minimum ~w~ such that ~G(w)~ is not bipartite (i.e. has an odd cycle).

There are multiple ways to solve this problem for graphs in ~\mathcal O(E \log E)~ time.

1. Binary search combined with a linear-time check on if a graph is bipartite.

2. Find the minimum spanning tree (MST), and use the 2-colouring of the tree. Let ~X~ be the answer we get with this algorithm, and ~OPT~, be the actual answer. Clearly ~X \le OPT~.

   However, we determined ~X~ by finding an edge of weight ~X~ between two nodes of the same colour. Using the path in the MST, this results in an odd cycle with all edges having weight at most ~X~, so ~OPT \le X~. Therefore ~X=OPT~.

3. We can use a variant of Kruskal's algorithm with an augmented disjoint-set data structure. The data structure needs to maintain a locally valid colouring of each component. This is a relatively standard idea with multiple ways to implement it.

   We add the edges in increasing order of weight, and using the data structure, we stop as soon as we have added an odd cycle.

For this subtask, it should be enough to use any of these approaches on the complete graph with weights equal to distances. The time complexity is ~\mathcal O(N^2 \log N)~.

Subtask 2

This subtask is intended for solutions that have complexity ~\mathcal O(N \log N)~ with a high constant factor.

Here I will present an approach that is ideal if you have access to a book of template geometry code. In this solution, you can use the relevant geometry algorithms as a black-box without understanding how they work.

The approach is to use the method we proved earlier of finding the minimum spanning tree, and using its 2-colouring. Given ~N~ points in the plane, it is a standard problem to find the Euclidean MST. A way to solve it is to use the fact that the Delaunay triangulation is guaranteed to contain the Euclidean MST. Since there is an algorithm to find the Delaunay triangulation in ~\mathcal O(N \log N)~ time (albeit with a high constant), we can find the 2-colouring in ~\mathcal O(N \log N)~. The last step is to find the closest pair of points for each colour. Again, we can use a black-box ~\mathcal O(N \log N)~ algorithm for this.

Subtask 3

There are several ways to solve the problem fully. The general approach is to efficiently find a subgraph with ~\mathcal O(N)~ edges that contains ~G(w)~ for some ~w~, so that ~G(w)~ is not bipartite. Then, we can run one of the ~\mathcal O(E \log E)~ graph algorithms to solve the problem in ~\mathcal O(N \log N)~ time. The hard part is finding a sufficiently high ~w~ such that ~G(w)~ only has ~\mathcal O(N)~ edges, and doing this efficiently. Indeed, it is not obvious why this is guaranteed to be possible with only ~\mathcal O(N)~ edges!

A good place to look for inspiration is in algorithms that find the closest pair of points in ~\mathcal O(N \log N)~ time. They use an important property: in a ~d \times d~ square, there can be at most ~\mathcal O(1)~ points before you get a pair within distance ~d~ of each other.

We can extend this to the following property: in a ~d \times d~ square, there can be at most ~\mathcal O(1)~ points before there is a triple of points such that all edges of the resulting triangle have length at most ~d~. This is useful because the existence of such a triangle implies that ~G(d)~ is not bipartite.

There are many ways to exploit this property, but here I will just describe one solution. The algorithm extends the line-sweep algorithm for finding the closest pair of points. It maintains a distance ~d~ that can only decrease, and a set of all points within distance ~d~ from the sweep-line. Given a point on the sweep-line, we can efficiently find all points within distance ~d~ of the point. If we maintain ~d~ correctly, there will be at most ~\mathcal O(1)~ such points. Then in ~\mathcal O(1)~ time we can loop through the points and see if there is a triangle with a smaller maximum edge length. If so, then we update our distance ~d~ accordingly. As we go, we can also directly construct our graph by adding edges from the point to every other point within distance ~d~. This algorithm runs in ~\mathcal O(N \log N)~ time.

Of course, there are other ways to find a good distance ~d~ and efficiently construct ~G(d)~. To pass this subtask, it is important to both have time complexity ~\mathcal O(N \log N)~ and a good constant factor.