利口 就留三

这道题类似于脑筋急转弯啊，最优解就是，利用矩形的两个对角线长度必然相等的特性，根据对角线长和中点位置做哈希存储。

1. class Solution {
   
2. private:
   
3.     unordered_map<string,vector<vector<int>>> mp;
   
4. public:
   
5.     double minAreaFreeRect(vector<vector<int>>& points) {
   
6.         int n=points.size();
   
7.         for(int i=0;i<n;i++)
   
8.         {
   
9.             for(int j=i+1;j<n;j++)
   
10.             {
    
11.                 int dx=points[i][0]-points[j][0];
    
12.                 int dy=points[i][1]-points[j][1];
    
13.                 long dist2=dx*dx+dy*dy;
    
14.                 double cx=(points[i][0]+points[j][0])*0.5;
    
15.                 double cy=(points[i][1]+points[j][1])*0.5;
    
16.                 string s=to_string(dist2)+": "+to_string(cx)+", "+to_string(cy);
    
17.                 mp[s].push_back({i,j});
    
18.             }
    
19.         }
    
20.         double min_area=1e15;
    
21.         for(auto it=mp.begin();it!=mp.end();it++)
    
22.         {
    
23.             if(it->second.size()<2) continue;
    
24.             //there could be multiple rectangle inside
    
25.             //now we have 4 points in diagonal, p0-p2 diagonal, p1-p3 diagonal
    
26.             vector<vector<int>>& vrect=it->second;
    
27.             for(int i=0;i<vrect.size();i++)
    
28.             {
    
29.                 for(int j=i+1;j<vrect.size();j++)
    
30.                 {
    
31.                     int p0=vrect[i][0],p2=vrect[i][1];
    
32.                     int p1=vrect[j][0],p3=vrect[j][1];
    
33.                     int dx=points[p0][0]-points[p1][0];
    
34.                     int dy=points[p0][1]-points[p1][1];
    
35.                     long long dist01=dx*dx+dy*dy;
    
36.                     dx=points[p0][0]-points[p3][0];
    
37.                     dy=points[p0][1]-points[p3][1];
    
38.                     long long dist03=dx*dx+dy*dy;
    
39.                     double area=sqrt(double(dist01)*dist03);
    
40.                     min_area=min(min_area,area);
    
41.                 }
    
42.             }
    
43.         }
    
44.         return min_area==1e15?0:min_area;
    
45.     }
    
46. };

复制代码

补充内容 (2018-12-24 08:59):
求加米！