1. Description
给定平面上的 n 个互不相同的整数坐标点，每个点表示为 (x, y)。
从中选择四个不同的点，如果满足以下条件，则称它们构成一个合法正方形：
- 四个点恰好是一个正方形的四个顶点。
- 正方形的四条边均平行于坐标轴，且边长大于 0。
- 除这四个顶点外，不存在其他给定点位于正方形内部或边界上。
请返回所有不同合法正方形的数量。
2. Solution
n = points.size()
Time complexity: O(n$^2$)
Space complexity: O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
| class Solution {
public:
int countSquares(vector<vector<int>>& points) {
const int n = points.size();
map<int, vector<int>> rows;
set<pair<int, int>> point_set;
for (const auto& point : points) {
int x = point[0], y = point[1];
rows[y].push_back(x);
point_set.emplace(x, y);
}
for (auto& [y, xs] : rows) {
sort(xs.begin(), xs.end());
}
int count = 0;
for (const auto& [y, xs] : rows) {
for (int i = 1; i < xs.size(); ++i) {
int x1 = xs[i - 1], x2 = xs[i];
long long d = 1LL * x2 - x1;
long long y2 = 1LL * y + d;
if (y2 > INT_MAX || y2 < INT_MIN) {
continue;
}
if (!point_set.contains({x1, static_cast<int>(y2)}) ||
!point_set.contains({x2, static_cast<int>(y2)})) {
continue;
}
bool valid = true;
for (const auto& point : points) {
long long x = point[0], py = point[1];
if (x1 <= x && x <= x2 &&
y <= py && py <= y2) {
bool is_corner =
(x == x1 || x == x2) &&
(py == y || py == y2);
if (!is_corner) {
valid = false;
break;
}
}
}
if (valid) {
++count;
}
}
}
return count;
}
};
|