# 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