ハムサンドイッチの定理より、平面をある直線で 2 分割して、どちらの領域にも \(P\) と \(Q\) がいずれも全体の半分ずつ存在するようにすることができます。この分割を再帰的に繰り返せば求めるマッチングが得られます。 以下のアルゴリズムにより、そのような直線を高速に計算できます。

• 角度 \(\theta\) を 1 つ定めると、その角度の直線であって、\(P\) を半分に分割する直線 \(L _ {\theta}\) が存在する。\(L _ {\theta}\) は \(P\) を射影して中央値を計算すれば求まる。
• \(\theta\) を徐々に変化させていくと \(L_{\theta}\) も徐々に変化する。\(L_{\theta}\) の左側に存在する \(Q\) の個数も徐々に変化するが、最初 \(k\) 個だったとすると \(\theta\) が \(\pi\) rad 変化したときは \(N-k\) 個になっているため、どこかで丁度半分になる瞬間が存在する。これは二分探索で求まる。

\(N\) が奇数のときと偶数のときでそれぞれ上記の議論に微妙な問題が発生しますが、省略します。 本問題のテストケースでは、このアルゴリズムを愚直に浮動小数点数 double で計算することで AC を得られるようです。厳密には、誤差について考える必要があります。 時間計算量は \(\Theta(N \log N \log X)\) です。

実装例: https://atcoder.jp/contests/abc373/submissions/58248165