问题：最小面积矩形

给定在 xy 平面上的一组点，确定由这些点组成的矩形的最小面积，其中矩形的边平行于 x 轴和 y 轴。

如果没有任何矩形，就返回 0。

示例 1：

输入：[[1,1],[1,3],[3,1],[3,3],[2,2]]
输出：4

示例 2：

输入：[[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]
输出：2

提示：

1. 1 <= points.length <= 500
2. 0 <=&nbsp;points[i][0] <=&nbsp;40000
3. 0 <=&nbsp;points[i][1] <=&nbsp;40000
4. 所有的点都是不同的。

**链接：https://leetcode-cn.com/contest/weekly-contest-110/problems/minimum-area-rectangle/**

分析：

1.四个点构成一个矩形，其中左下坐标（x1,y1），右上坐标(x2,y2)，则另外两个坐标为(x1,y2) (x2,y1)

2.可以逐一遍历所有点，得到以该点为左下角的最小面积，其其中的最小者。

3.获取以某个点为左下角的所有矩形最小面积时候，对于该点（x1,y1）,先得到所有的（x1，ym）和（xn，y1），查看(xn，ym)是否在给出的点中，如果是则可以构成矩形，否则不可以，如果构成矩形，面积为（xn-x1）*(ym-y1)

4.对所有的（X1，y）和（x，Y1）排序后，假设选择了（x1，yi）和（xn，y1）两个点且（xn，yi)在给出的点中那么对于后续的（x1,yi+1）和（xn,y1）都不用看了，即使构成了矩形面积也大于(x1,yi)，而且对于后续的(x1,yi+1)进行尝试的时候，只需要查看{(xm,y1)，m<n}面积是否更小即可。

如图中所示，最小面积只能在(xi,yi)和（xi-,yi+）之中选择较小者。【对于固定的Xi，如果Yi能构成面积，Yi+即使能够成，得到的面积也会更大，而对于Yi+，如果X>Xi,则（X ,Yi）的面积必定大于（Xi,Yi）】

AC Code：

class Solution
{
public:
int minAreaRect(vector>& points)
{
int ret = INT_MAX;
sort(points.begin(), points.end());
for (int i = 0; i < points.size(); i++) { vector > getxs;
vector > getys;
//得到X值相同的点
getxs = GetXs(points, i+1, points[i]);
//得到Y值相同的点
getys = GetYs(points, i + 1, points[i]);
if (getxs.size() == 0 || getys.size() == 0)
{
continue;
}
int tmparea = GetMiniRect(points, getxs, getys, points[i]);
if (ret > tmparea)
{
ret = tmparea;
}

    }  
    if (ret == INT\_MAX)  
    {  
        ret = 0;  
    }  
    return ret;  
}  
int GetMiniRect(vector<vector<int> > points, vector<vector<int> > Xs, vector<vector<int> > Ys, vector<int> startpoint)  
{  
    int ret = INT\_MAX;  
    vector<int> tmpx;  
    vector<int> tmpy;  
    //一条水平线上的，按照y排序  
    //sort(Xs.begin(), Xs.end(), cmpY);  
    //一条竖直线上的，按照x排序  
    //sort(Ys.begin(), Ys.end(), cmpX);

    int x1, y1, x2, y2;  
    x1 = startpoint\[0\];  
    y1 = startpoint\[1\];

    int jend = Ys.size();  
    for (int i = 0; i < Xs.size(); i++)  
    {  
        y2 = Xs\[i\]\[1\];  
        for (int j = 0; j < Ys.size() && j<jend; j++)  
        {  
            x2 = Ys\[j\]\[0\];  
            vector<int> tmp = vector < int > {x2, y2};  
            if (std::find(points.begin(), points.end(), tmp) != points.end())  
            {  
                int local = (x2 - x1)\*(y2 - y1);  
                if (ret > local)  
                {  
                    ret = local;  
                }  
                jend = j;  
                break;  
            }  
            else  
            {  
                continue;  
            }  
        }  
    }

    return ret;  
}  
vector<vector<int> > GetXs(vector<vector<int> > points, int begin, vector<int> target)  
{  
    vector<vector<int> > ret;  
    for (int i = begin; i < points.size(); i++)  
    {  
        if (points\[i\] == target)  
        {  
            continue;  
        }  
        if (points\[i\]\[0\] == target\[0\] && points\[i\]\[1\] > target\[1\])  
        {  
            ret.emplace\_back(points\[i\]);  
        }  
    }  
    return ret;  
}  
vector<vector<int> > GetYs(vector<vector<int> > points, int begin, vector<int> target)  
{  
    vector<vector<int> > ret;  
    for (int i = begin; i < points.size(); i++)  
    {  
        if (points\[i\] == target)  
        {  
            continue;  
        }  
        if (points\[i\]\[1\] == target\[1\] && points\[i\]\[0\] > target\[0\])  
        {  
            ret.emplace\_back(points\[i\]);  
        }  
    }  
    return ret;  
}

};

其他：

1.对于多重vector，比如vector >执行sort函数后，会自动对所有元素都进行排序，即每个vector内部也会排序，做题的时候不确定这个，还特意编写自定义排序。

2.最开始考虑到（1X5 5X1 2X2）面积中2X2最小，做的是双重循环O（n*n）超时，考虑到沿着Y轴进行尝试，一旦得到一个矩形，X的上限就确定了，数据量大大减少

3.过程中遇到本地运行调试都对，提交提示内存地址对齐错误，最终发现是由于数字访问越界，而定位问题的方法则是提交试错：通过删减代码，定位到当有x2 = Ys[i][0];语句存在时候提交就会报这样的错误，实际上应该是x2 = Ys[j][0];。