算法
(几何、暴力枚举) $O(N^2\log N)$
枚举矩形的左下顶点和右上顶点,判断相应的左上顶点和右下顶点是否存在。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::set;
using std::vector;
using P = std::pair<int, int>;
int main() {
int n;
cin >> n;
vector<int> x(n), y(n);
rep(i, n) cin >> x[i] >> y[i];
set<P> s;
rep(i, n) s.emplace(x[i], y[i]);
int ans = 0;
rep(i, n)rep(j, n) {
int xi = x[i], xj = x[j];
int yi = y[i], yj = y[j];
if (xi < xj and yi < yj) {
if (s.find(P(xi, yj)) == s.end()) continue;
if (s.find(P(xj, yi)) == s.end()) continue;
++ans;
}
}
cout << ans << '\n';
return 0;
}
Python 代码
n = int(input())
points = set()
for i in range(n):
x, y = map(int, input().split())
points.add((x, y))
ans = 0
for p1 in points:
for p2 in points:
if p1[0] >= p2[0] or p1[1] >= p2[1]:
continue
if (p1[0], p2[1]) in points and (p2[0], p1[1]) in points:
ans += 1
print(ans)