atulsingh7890

Minimum Area Rectangle

Oct 5th, 2020
54
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.40 KB | None | 0 0
  1. //https://leetcode.com/problems/minimum-area-rectangle/
  2.  
  3. class Solution {
  4. public:
  5.     int minAreaRect(vector<vector<int>>& points) {
  6.         std::set<std::pair<int,int>> point_set;
  7.         for(auto & point : points) {
  8.             point_set.insert({point[0], point[1]});
  9.         }
  10.        
  11.         int min_area = std::numeric_limits<int>::max();
  12.         for(int i = 0; i < points.size(); ++i) {
  13.             for(int j = i+1; j < points.size(); ++j) {
  14.                 std::pair<int,int>  lower_left{points[i][0], points[i][1]};
  15.                 std::pair<int,int>  top_right{points[j][0], points[j][1]};
  16.                 if(lower_left.first != top_right.first && lower_left.second != top_right.second) {
  17.                     //check if corresponding
  18.                     std::pair<int,int> top_left{lower_left.first, top_right.second};
  19.                     std::pair<int,int> bottom_right{top_right.first, lower_left.second};
  20.                     if(point_set.find(top_left) != point_set.end() &&
  21.                       point_set.find(bottom_right) != point_set.end()) {
  22.                         min_area = std::min(min_area, std::abs(lower_left.first - bottom_right.first)
  23.                                             *std::abs(lower_left.second - top_left.second));
  24.                     }
  25.                 }
  26.             }
  27.         }
  28.         return min_area != std::numeric_limits<int>::max() ? min_area : 0;
  29.     }
  30. };
Add Comment
Please, Sign In to add comment