Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //https://leetcode.com/problems/minimum-area-rectangle/
- class Solution {
- public:
- int minAreaRect(vector<vector<int>>& points) {
- std::set<std::pair<int,int>> point_set;
- for(auto & point : points) {
- point_set.insert({point[0], point[1]});
- }
- int min_area = std::numeric_limits<int>::max();
- for(int i = 0; i < points.size(); ++i) {
- for(int j = i+1; j < points.size(); ++j) {
- std::pair<int,int> lower_left{points[i][0], points[i][1]};
- std::pair<int,int> top_right{points[j][0], points[j][1]};
- if(lower_left.first != top_right.first && lower_left.second != top_right.second) {
- //check if corresponding
- std::pair<int,int> top_left{lower_left.first, top_right.second};
- std::pair<int,int> bottom_right{top_right.first, lower_left.second};
- if(point_set.find(top_left) != point_set.end() &&
- point_set.find(bottom_right) != point_set.end()) {
- min_area = std::min(min_area, std::abs(lower_left.first - bottom_right.first)
- *std::abs(lower_left.second - top_left.second));
- }
- }
- }
- }
- return min_area != std::numeric_limits<int>::max() ? min_area : 0;
- }
- };
Add Comment
Please, Sign In to add comment