LeetCode 963. 最小面积矩形 II

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

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

示例 3：
输入：[[0,3],[1,2],[3,1],[1,3],[2,1]]
输出：0
解释：没法从这些点中组成任何矩形。

示例 4：
输入：[[3,1],[1,1],[0,1],[2,1],[3,3],[3,2],[0,2],[2,3]]
输出：2.00000
解释：最小面积的矩形出现在 [2,1],[2,3],[3,3],[3,1] 处，面积为 2。
 
提示：
1 <= points.length <= 50
0 <= points[i][0] <= 40000
0 <= points[i][1] <= 40000
所有的点都是不同的。
与真实值误差不超过 10^-5 的答案将视为正确结果。

class point{
public:
	int x, y;
	point(int x, int y)
	{
		this->x = x;
		this->y = y;
	}
    bool operator<(point a) const
    {
        return (x==a.x && y < a.y) || (x < a.x);
    }
};
class Solution {
public:
    double minAreaFreeRect(vector<vector<int>>& points) {
    	map<int,map<point,vector<point>>> m;// square len, midpoint, point
    	int n = points.size(), x1,x2,y1,y2,x3,y3,d;
    	int midx, midy;
    	for(int i = 0; i < n; ++i)
    	{
    		for(int j = i+1; j < n; ++j)
    		{
    			x1 = points[i][0];
    			y1 = points[i][1];
    			x2 = points[j][0];
    			y2 = points[j][1];
    			midx = (x1+x2);//不除以2
    			midy = (y1+y2);
    			d = dis(x1,y1,x2,y2);
    			m[d][point(midx, midy)].push_back(point(x1,y1));
    		}
    	}
    	double area = INT_MAX;
    	int dx1,dy1,dx2,dy2;
    	for(auto it = m.begin(); it != m.end(); ++it)
    	{
    		for(auto it1 = it->second.begin(); it1 != it->second.end(); ++it1)
    		{
    			midx = it1->first.x;
    			midy = it1->first.y;
    			for(int i = 0; i < it1->second.size(); ++i)
    			{
    				x1 = it1->second[i].x;
    				y1 = it1->second[i].y;
    				x2 = midx-x1;
    				y2 = midy-y1;
    				for(int j = i+1; j < it1->second.size(); ++j)
    				{
    					x3 = it1->second[j].x;
    					y3 = it1->second[j].y;
    					dx1 = x1-x3, dy1 = y1-y3;
    					dx2 = x2-x3, dy2 = y2-y3;
    					if(dx1*dx2+dy1*dy2==0)
    					{
    						area = min(area, sqrt(dx1*dx1+dy1*dy1)*sqrt(dx2*dx2+dy2*dy2));
    					}
    				}
    			}
    		}
    	}
    	return area == INT_MAX ? 0 : area;
    }
    int dis(int x1, int y1, int x2, int y2)
    {
    	return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
    }
};