Find the total area covered by two rectilinear rectangles in a 2D plane.
Each rectangle is defined by its bottom left corner and top right corner as shown in the figure.
Example:
<pre style="box-sizing: border-box; font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, Courier, monospace; font-size: 13px; margin-top: 0px; margin-bottom: 1em; overflow: auto; background: var(--dark-bg); border-color: rgb(51, 51, 51); color: var(--font) !important; padding: 10px 15px; line-height: 1.6; border-radius: 3px; white-space: pre-wrap;">Input: A = -3, B = 0, C = 3, D = 4, E = 0, F = -1, G = 9, H = 2
Output: 45</pre>
Note:
Assume that the total area is never beyond the maximum possible value of int.
这道题抛开long的坑不谈，我一开始就想错方向了，试图去分类讨论，找哪些点，有几个点被互相包括，1个点包括的话怎么算，2个点包括怎么办， 4个点包括怎么办，0个点包括怎么办。
结果搞不完的edge cases。比如inclusion函数得是闭区间，否则会判断出0个点包含。但是有可能有left在right里面，但是left的边缘也在right边缘的情况，需要开区间。
就算都修复完成，还有一个case是十字交叉... 真修复不完了！
所以还是感觉写代码量太大的情况下，早点看答案！
自己写的答案：
class Solution {
public:
int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
int cross_area = max(
CrossArea(A,B,C,D,E,F,G,H), CrossArea(E,F,G,H,A,B,C,D)
);
// cout << CrossArea(A,B,C,D,E,F,G,H) << ", " << CrossArea(E,F,G,H,A,B,C,D) << endl;
long ans = (C-A)*(D-B) + (G-E)*(H-F) - cross_area;
return ans;
}
int CrossArea (int A, int B, int C, int D, int E, int F, int G, int H) {
vector<pair<int,int>> points_left = FourPoints(A,B,C,D);
vector<pair<int,int>> points_right = FourPoints(E,F,G,H);
vector<pair<int,int>> right_included;
for (auto& p:points_left) {
if (Inclusion(p,E,G,F,H)) {
right_included.push_back(p);
}
}
int right_inclusion_num = right_included.size();
if (right_inclusion_num == 4) {
return (C-A)*(D-B);
}
else if (right_inclusion_num == 1) {
for (auto& p:points_right) {
if (Inclusion(p,A,C,B,D)) {
return abs(p.first-right_included[0].first)
*abs(p.second-right_included[0].second);
}
}
}
else if (right_inclusion_num == 2) {
int x_min = min(right_included[0].first, right_included[1].first);
int x_max = max(right_included[0].first, right_included[1].first);
int y_min = min(right_included[0].second, right_included[1].second);
int y_max = max(right_included[0].second, right_included[1].second);
if (x_min == x_max) {
for (auto& p:points_right) {
if (Inclusion(p,A,C,INT_MIN,INT_MAX)) {
return (y_max-y_min)*abs(x_min-p.first);
}
}
}
else if (y_min == y_max) {
for (auto& p:points_right) {
if (Inclusion(p,INT_MIN,INT_MAX,B,D)) {
return (x_max-x_min)*abs(y_min-p.second);
}
}
}
}
return 0;
}
vector<pair<int,int>> FourPoints(int& A, int& B, int& C, int& D) {
return {{A,B}, {C,B}, {C,D}, {A,D}};
}
bool Inclusion(pair<int,int>& point, int x_min_bound, int x_max_bound, int y_min_bound, int y_max_bound) {
return (
point.first >= x_min_bound and
point.first <= x_max_bound and
point.second >= y_min_bound and
point.second <= y_max_bound
);
}
};
虽然完全想偏了，但是其中几个语法错误需要思考：
- 函数foo(int& a) 的输入不能是rvalue，比如foo(1)就完全错了！
- const auto&，或者比如const int&会把变量转成const int&的类型，所以不能进一步foo(var)处理这个值
void foo(int& j); //报错，得改成void foo(const int& j);
int main(){
int i = 1;
const int& j = i;
cout << j << endl;
foo(j);
return 0;
}
https://www.youtube.com/watch?v=N1BSWQyHJ3E
这道题还有一个巨坑在中间变量可能超int，所以所有都转成long才行，包括int
最后我的默写：
class Solution {
public:
int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
long A_=A, B_=B, C_=C, D_=D, E_=E, F_=F, G_=G, H_=H;
long cross_area = max((long)0, min(C_,G_)-max(A_,E_))*max((long)0, min(D_,H_)-max(B_,F_));
int ans = (C_-A_)*(D_-B_) + (G_-E_)*(H_-F_) - cross_area;
return ans;
}
};
Runtime: 4 ms, faster than 91.44% of C++ online submissions for Rectangle Area.
Memory Usage: 6.2 MB, less than 73.91% of C++ online submissions for Rectangle Area.
拓展：
836这道题
也就是一行解决：
- rect1左下角的x必须小于rect2右上角的x （rect1的x_min < rect2的x_max）
- rect1右上角的x必须大于rect2左下角的x（rect1的x_max > rect2的x_min）
- rect1左下角的y必须小于rect2右上角的y（rect1的y_min < rect2的y_max）
- rect1右上角的y必须大于rect2左下角的y（rect1的y_max > rect2的y_min）
其实就是排除了 x y 分别完全在两侧的情况，排除法。
https://www.youtube.com/watch?v=UUjeqglXaSQ
网友评论