nikunjsoni

963

Jul 26th, 2021
125
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     size_t d2(int x1, int y1, int x2, int y2) {
  4.       return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
  5.     }
  6.    
  7.     double minAreaFreeRect(vector<vector<int>>& ps, size_t res = 0) {
  8.         unordered_map<size_t, unordered_map<size_t, vector<vector<int>>>> m;
  9.      
  10.         for(auto i = 0; i < ps.size(); ++i)
  11.         for(auto j = i + 1; j < ps.size(); ++j) {
  12.           auto center = (size_t(ps[i][0] + ps[j][0]) << 16) + ps[i][1] + ps[j][1];
  13.           auto len = d2(ps[i][0], ps[i][1], ps[j][0], ps[j][1]);
  14.           m[center][len].push_back({ps[i][0], ps[i][1], ps[j][0], ps[j][1]});
  15.         }
  16.        
  17.         for(auto it_c = begin(m); it_c != end(m); ++it_c)
  18.             for(auto it_l = begin(it_c->second); it_l != end(it_c->second); ++it_l)
  19.                 for(auto i = 0; i < it_l->second.size(); ++i)
  20.                     for(auto j = i + 1; j < it_l->second.size(); ++j) {
  21.                         auto &p1 = it_l->second[i], &p2 = it_l->second[j];
  22.                         auto area = d2(p1[0], p1[1], p2[0], p2[1]) * d2(p1[0], p1[1], p2[2], p2[3]);
  23.                         if(res == 0 || res > area) res = area;
  24.                     }
  25.         return sqrt(res);
  26.     }
  27. };
RAW Paste Data