题目描述 最小面积矩形 II

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

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

示例 1：

输入：[[1,2],[2,1],[1,0],[0,1]]
输出：2.00000
解释：最小面积的矩形出现在 [1,2],[2,1],[1,0],[0,1] 处，面积为 2。

解题思路

嗯，反正想了半天也不会。
然后就只能看看大神们的想法了。参考
长方形判定定理：对角线相等，且互相平分的四边形是矩形。

• 首先平方枚举两个点所构成的所有线段。
• 对于这些线段把它们当做长方形的一条对角线，确定了这条对角线之后。枚举第三个点，首先判断第三个点到对角线中点的距离是不是满足对角线长度的一半，（比较距离）。
• 然后判断，与这三个点构成矩形的第四个点是不是存在：如何判断第四个点存不存在呢？假设p1,p2,p3是已知的三个点。p1,p2构成对角线，对角线的中点是(a,b)。那么第四个点的坐标为：p3.x + (p3.x - a),p3.y + (p3.y - b).其中p3.x-a是p3到中点X轴方向的L1距离，仔细体会一下~。用一个map存一下所有的点就可以判断这个点在不在集合内了。
• 如果以上两个判断都成立，那么算该长方形的面积（四个点都有了，算出长宽之积就ok）
  用一个全局变量存满足条件的矩形的最小值就好。

代码

class Solution {
public:
    double era=1e-7;
    map<pair<double,double>,int>ma;
    double minAreaFreeRect(vector<vector<int>>& points) {
            double ans=0x3f3f3f3f;
            for (int i=0;i<points.size();i++)
            {
                ma[pair<double,double>((double)points[i][0],(double)points[i][1])]=1;
            }
            for (int i=0;i<points.size();i++)
            {
                for (int j=i+1;j<points.size();j++)
                {
                    double x1=points[i][0],y1=points[i][1],x2=points[j][0],y2=points[j][1];
                    double x=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
                    double centerx=(x1+x2)*1.0/2,centery=(y1+y2)*1.0/2;
                    for (int k=j+1;k<points.size();k++)
                    {
                        double x3=points[k][0],y3=points[k][1];
                        double dis=sqrt((x3-centerx)*(x3-centerx)+(y3-centery)*(y3-centery));
                        if(fabs(dis*2-x)<era)
                        {

                            double x4=centerx*2-x3,y4=2*centery-y3;
                            if(ma[pair<double,double>(x4,y4)])
                            {
                                double area=sqrt((x1-x3)*(x1-x3)+(y1-y3)*(y1-y3))*sqrt((x1-x4)*(x1-x4)+(y1-y4)*(y1-y4));
                                ans=min(ans,area);
                            }
                        }
                    }
                }
            }
        if(ans==0x3f3f3f3f)
            return 0;
        else 
            return ans;
    }
};