この問題は \(O(N \sqrt N)\) でも解くことができます。

長方形の \(2\) つの \(y\) 座標を \(y_1, y_2\) と固定したとき、長方形の個数は、\((x, y_1),(x,y_2)\) の \(2\) 点があるような \(x\) の個数を \(K\) として、\(\dfrac{K(K-1)}{2}\) 個です。 これを踏まえると、\(N\) 個の点を \(x\) 座標でグループ分けし、同じグループから \((y_1, y_2)\) を選んでそれぞれの出現回数を数えることで、\(O(N^2)\) で解くことができます。

回答例 (Python)

また、各グループの大きさが \(\sqrt N\) 以下であれば、上のアルゴリズムは \(O(N\sqrt N)\) になります。そこで、大きさが \(\sqrt N\) より大きいグループについては別の方法で数えます。

グループを \(G_x\) と書くことにします。
\(|G_{x_1}| > \sqrt N\) であるような \(x\) 座標 \(x_1\) と、そうとは限らない \(x_2\) を固定すると、長方形の個数は、\(K = |G_{x_1} \cap G_{x_2}|\) として、\(\dfrac{K(K-1)}{2}\) 個です。\(2\) つのグループの積集合の大きさは \(G_{x_1}\) 側で前計算をしておくことによって、\(O(|G_{x_2}|)\) で計算することができ、\(x_2\) を全探索したとき、\(x_1\) ごとに \(O(N)\) で長方形の個数を計算できます。 \(|G_x| > \sqrt N\) であるようなグループの個数は \(\sqrt N\) 以下なので、全体で \(O(N \sqrt N)\) で解くことができました。

回答例 (C++)