(これは、公式解説の2枚目です。)

以下の解法について検討してみましょう。

1. 平面全体を ランダムに 回転させる。より厳密には適当な点に原点をとり、そこを基準としてある実数 \(\theta \in [0,2 \pi)\) を定め、平面全体を \(\theta\)[rad] 回転させる。
2. 回転させたあとの平面で、 \(x\) 座標の差が \(K\) 以下の点の組に対してのみ全探索を行う。

期待される計算量はどの程度でしょうか?

\(i\) 個目の点と \(j\) 個目の点との距離を \(d_{i,j}\) とすると、それらの点の \(x\) 座標の差が \(K\) 以下になる確率は \(\arcsin(\min(1,\frac{K}{d_{i,j}})) / (\pi/2)\) です。
点の \(x\) 座標の差が \(K\) 以下である組の個数の期待値は、この確率を足し上げた \(\sum_{i<j} \arcsin(\min(1,\frac{K}{d_{i,j}})) / (\pi/2)\) となります。
また、 \(0\) 以上の実数 \(\alpha\) に対して \(\arcsin(\alpha) / (\pi/2) \le \alpha\) であるため、この期待値は \(\sum_{i<j} \min(1,\frac{K}{d_{i,j}})\) 以下です。

さらに評価を続けます。先程の期待値は、 (距離 \(2K\) 以下の点の組の数) \(+\) \(\frac{1}{2} \times\) (距離 \(4K\) 以下の点の組の数) \(+\) \(\frac{1}{4} \times\) (距離 \(8K\) 以下の点の組の数) \(\dots\) で上から抑えられます。
さらに、(距離 \(cK\) 以下の点の組の数) は \(c^2(N+M)\) 程度で上から抑えられます。 これより、評価するべき点の組の数の期待値は \(\sum_{c=2^i,i \in \mathbb{N}}\frac{1}{c} \times \min(c^2(N+M),N^2)\) 程度で抑えられ、\(c = \sqrt{(N+M)}\) 付近を境界として \(\min\) である側が入れ替わることを利用して評価すると \(O((N+M)^{1.5})\) であることが分かります。

よって、ギリギリですが計算量的には間に合うという見積もりが示されました。 実際は単純な二重ループの枝刈り高速化のような形になるので、この方針でも十分AC可能です。
なお、回転の中心や回転角を乱択する際、回転をかけた後に調べるべき点の組の総数だけを尺取り法により \(O(N)\) で求めることができるので、何度か回転の中心や回転角を乱択した上で最も調べるべき点の組が少ない状況についてこの解法を実行するといったことができます。