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
| #include <vector>
using namespace std;
long long minWidth(vector<long long>& A, vector<long long>& B) {
long long y1 = INT_MIN, res = INT_MAX;
long long i = 0, j = 0, n = A.size(), m = B.size();
while(i < n and j < m) {
if(A[i] == B[j]) {
res = min(res, abs(y1 - A[i]));
y1 = A[i];
i++,j++;
} else if(A[i] < B[j]) {
i++;
} else {
j++;
}
}
return res;
}
int minimumAreaRectangle(vector<vector<int>> points) {
long long res = INT_MAX;
unordered_map<long long, vector<long long>> mp;
for(auto& point : points) {
mp[point[0]].push_back(point[1]);
}
for(auto& [_, xaxis] : mp) {
sort(begin(xaxis), end(xaxis));
}
for(auto i = begin(mp); i != end(mp); i++) {
for(auto j = next(i); j != end(mp); j++) {
long long height = abs(i->first - j->first);
long long width = minWidth(i->second, j->second);
res = min(res, height * width);
}
}
return res == INT_MAX ? 0 : res;
}
|
