左下の頂点と右上の頂点を決めると長方形が一意に定まることを利用します。

まず、左下の頂点と右上の頂点の組を全探索し、それぞれに対応する左上と右下の頂点が \(N\) 個の点に含まれるかを判定します。ある点が \(N\) 個の点に含まれているかの判定は、事前に点をソートしておくことで、二分探索を用いて \(O(\log N)\) で求められます。事前に座標圧縮しておくと \(O(1)\) で求めることもできます。

実装例 (C++)

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n; cin >> n;
    vector<pair<int,int>> v(n);
    for(int i = 0; i < n; i++) cin >> v[i].first >> v[i].second;
    sort(v.begin(), v.end());
    int ans = 0;
    for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) if(v[i].first < v[j].first && v[i].second < v[j].second) {
        if(binary_search(v.begin(), v.end(), make_pair(v[i].first, v[j].second)) && binary_search(v.begin(), v.end(), make_pair(v[j].first, v[i].second))) ans++;
    }
    cout << ans << endl;
}