【每日一算法】矩形面积
微信改版,加星标不迷路!
每日一算法-矩形面积
作者:阿广
阅读目录
1 题目
2 解析
1 题目
在二维平面上计算出两个由直线构成的矩形重叠后形成的总面积。
每个矩形由其左下顶点和右上顶点坐标表示,如图所示。
示例:
输入: -3, 0, 3, 4, 0, -1, 9, 2
输出: 45
说明: 假设矩形面积不会超出 int 的范围。
2 解析
这个思路太棒啦~抓紧写下来!
首先判断两个矩形有没有重合,如果没有重合,直接返回两个矩形的面积之和。
如果有重合,则求重合的部分,奇妙之处来了!
将两个矩形的横坐标进行排序(一共四个横坐标),两个矩形的纵坐标进行排序(一共四个纵坐标)。
则S(重合部分) = (横坐标[2] - 横坐标[1]) * (纵坐标[2] - 纵坐标[1]);
总面积 = 两个矩形面积和 - S(重合部分);
下面用代码看一下:
判断两个矩形有没有重合,如果没有重合,直接返回两个矩形的面积之和。
int total = (C-A)*(D-B) + (G-E)*(H-F);
if(C<=E || G<=A || B>=H || D<=F){
return total;
}
将两个矩形的横坐标进行排序(一共四个横坐标),两个矩形的纵坐标进行排序(一共四个纵坐标)。
vector<int> h;
h.push_back(A);
h.push_back(C);
h.push_back(E);
h.push_back(G);
vector<int> v;
v.push_back(B);
v.push_back(D);
v.push_back(F);
v.push_back(H);
sort(v.begin(),v.end());
sort(h.begin(),h.end());
则S(重合部分) = (横坐标[2] - 横坐标[1]) * (纵坐标[2] - 纵坐标[1]);
总面积 = 两个矩形面积和 - S(重合部分);
total = total - (h[2] - h[1]) * (v[2] - v[1]);
return total;
3 完整代码
class Solution {
public:
int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
int total = (C-A)*(D-B) + (G-E)*(H-F);
if(C<=E || G<=A || B>=H || D<=F){
return total;
}else{
vector<int> h;
h.push_back(A);
h.push_back(C);
h.push_back(E);
h.push_back(G);
vector<int> v;
v.push_back(B);
v.push_back(D);
v.push_back(F);
v.push_back(H);
sort(v.begin(),v.end());
sort(h.begin(),h.end());
total = total - (h[2] - h[1]) * (v[2] - v[1]);
return total;
}
}
};
今日问题
人人自媒体的时代,你如何看待抖音、B站?
打卡格式:打卡第n天,答:...