给一系列顶点，计算这些点能组成矩形的最小面积
1. 最小面积矩形（列举对角线+哈希）
矩形的边平行于x轴和y轴
通过双重循环列举对角线顶点，计算满足条件的矩形面积
class Solution {
public:
int minAreaRect(vector<vector<int>>& points) {
set<pair<int,int>> s;
for(auto&point:points)
s.insert({point[0],point[1]});
int n = points.size();
int res = INT_MAX;
for(int i=0;i<n;i++){
int x1 = points[i][0]; int y1 = points[i][1];
for(int j=i+1;j<n;j++){
int x2 = points[j][0]; int y2 = points[j][1];
if(x1==x2||y1==y2) continue;
if(s.count({x1,y2})&&s.count({x2,y1}))
res = min(res,abs((x2-x1)*(y2-y1)));
}
}
return res==INT_MAX?0:res;
}
};
2. 最小面积矩形II(枚举三角形+哈希)
这里直接枚举所有顶点当三角形直角边顶点，就无需再判断和讨论
class Solution {
public:
double minAreaFreeRect(vector<vector<int>>& points) {
int n = points.size();
double res = INT_MAX;
set<pair<int,int>> s;
for(auto&point:points)
s.insert({point[0],point[1]});
for(int i=0;i<n;i++){ //列举对角线上的点
int x1 = points[i][0]; int y1 = points[i][1];
for(int j=0;j<n;j++){//枚举另外两侧的点
if(j==i) continue;
int x2 = points[j][0]; int y2 = points[j][1];
for(int k=j+1;k<n;k++){//枚举另外两侧的点
if(k==i) continue;
int x3 = points[k][0]; int y3 = points[k][1];
int product = (x2-x1)*(x3-x1)+(y2-y1)*(y3-y1);//计算内积
if(product!=0) continue;
int x4 = x2+x3-x1; int y4 = y2+y3-y1;//向量运算
if(s.count({x4,y4})){
double area = sqrt(pow(x2-x1,2)+pow(y2-y1,2))*sqrt(pow(x3-x1,2)+pow(y3-y1,2));
res = min(res,area);
}
}
}
}
return res==INT_MAX?0:res;
}
};