963. Minimum Area Rectangle II

题解

矩形的判断条件：1. 对角线的中点重合。2. 对角线长度相同。
对于一组点i，点j，计算获取到对应的中点和对角线长度。
然后按照所有的中点、对角线长度排序，相同的会放在一起。
我们一段段去计算，获取最小的面积值。
由于点是不重复的，所以不会出现对角线中点重合、对角线长度相同，并且面积为0的情况。
最后特判下是否一定有解。

代码

  1. class Solution {
  2. public:
  3.     typedef long long LL;
  4.     LL get_dist(vector<int> p1, vector<int> p2) {
  5.         LL x1 = p1[0], y1 = p1[1];
  6.         LL x2 = p2[0], y2 = p2[1];
  7.         return (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1);
  8.     }
  10.     int get_midium(int x1, int x2) {
  11.         return (x1 + x2) / 2;
  12.     }
  14.     double minAreaFreeRect(vector<vector<int>>& points) {
  15.         for (auto &p : points) {
  16.             p[0] *= 2;
  17.             p[1] *= 2;
  18.         }
  19.         vector<vector<LL>> info;
  20.         int n = points.size();
  21.         for (int i = 0; i < n; i ++) {
  22.             for (int j = i + 1; j < n; j ++) {
  23.                 int x1 = points[i][0], y1 = points[i][1];
  24.                 int x2 = points[j][0], y2 = points[j][1];
  25.                 info.push_back({get_midium(x1, x2), get_midium(y1, y2), get_dist(points[i], points[j]), i, j});
  26.             }
  27.         }
  28.         sort(info.begin(), info.end());
  29.         double ans = 1e20;
  30.         for (int i = 0; i < info.size(); i ++) {
  31.             int j = i + 1;
  32.             while(j < info.size() && info[i][0] == info[j][0] && info[i][1] == info[j][1] && info[i][2] == info[j][2]) {
  33.                 j ++;
  34.             }
  35.             for (int p = i; p < j; p ++) {
  36.                 for (int q = p + 1; q < j; q ++) {
  37.                     int pi = info[p][3], pj = info[p][4];
  38.                     int qi = info[q][3], qj = info[q][4];
  39.                     ans = min(ans, sqrt(get_dist(points[pi], points[qj])) * sqrt(get_dist(points[pi], points[qi])));
  40.                 }
  41.             }
  42.         }
  43.         if (ans == 1e20) {
  44.             return 0;
  45.         }
  46.         return ans / 4;
  47.     }
  48. };