(This is the second page of Official Editorial.)

Let’s consider the following solution.

1. Rotate entire plane by a random degree. Formally, take an arbitrary point as the origin, determine a real number \(\theta \in [0,2 \pi)\), and rotate entire plane by \(\theta\)[rad].
2. After the plane is rotated, exhaustively search for all pairs of points whose difference of \(x\) coordinates are at most \(K\).

What is the expected time complexity?

Let \(d_{i,j}\) be the distance between the \(i\)-th and the \(j\)=th points, then the probability that the difference of their \(x\) coordinates becomes less than \(K\) is \(\arcsin(\min(1,\frac{K}{d_{i,j}})) / (\pi/2)\).
The number of pairs of points whose differences of their \(c\) coordinates is less than \(K\) is the sum of the probability, \(\sum_{i<j} \arcsin(\min(1,\frac{K}{d_{i,j}})) / (\pi/2)\).
Also, for a real number \(\alpha\) greater than or equal to \(0\), \(\arcsin(\alpha) / (\pi/2) \le \alpha\), so the expected value is less than or equal to \(\sum_{i<j} \min(1,\frac{K}{d_{i,j}})\).

Let’s continue the evaluation. The upper bound of the last expected value is (the number of pairs of points with distances less than \(2K\)) \(+\) \(\frac{1}{2} \times\) (the number of pairs of points with distances less than \(4K\)) \(+\) \(\frac{1}{4} \times\) (the number of pairs of points with distances less than \(8K\)) \(\dots\).
Moreover, the upper bound of (the number of pairs of points with distances less than \(cK\)) is about \(c^2(N+M)\). Therefore, the expected value of number of points to be evaluated is bounded by \(\sum_{c=2^i,i \in \mathbb{N}}\frac{1}{c} \times \min(c^2(N+M),N^2)\). Using the fact that the \(\min\) side switches at the boundary around \(c = \sqrt{(N+M)}\), it can be evaluated as \(O((N+M)^{1.5})\).

Therefore, it is evaluated that it barely fits in the time limit, in terms of complexity. In fact, it will be like a optimization by pruning of simple double loop, so the solution is fast enough to be accepted.
Note that, after choosing the center and the degree of rotation, the number of pairs to be inspected can be computed in an \(O(N)\) time with sliding window technique, so we can try several candidates of centers and degrees and choose the ones which requires the smallest number of enumeration before executing the solution.