Given a list of coordinates, find the rectangle with minimal area Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)Std lib-like C++ function to find nearest elements in a containerFind Triangle Triplets from a list of given numbersFind non duplicateTriangle Triplets from a list of given numbersCalculating the area of a circleCalculate area and perimeter for shapes: polygon, circle, rectangle and triangle - follow upAnother way to find the nearest neighbor points in a 2D planeShifting the origin of a large list of coordinatesFinding non-self-intersecting paths of certain moves that touch all points in a gridPortability in using up-and-coming library featuresFind the first palindrome larger than the given number

Limit for e and 1/e

Writing Thesis: Copying from published papers

Why does this iterative way of solving of equation work?

Estimated State payment too big --> money back; + 2018 Tax Reform

What are the performance impacts of 'functional' Rust?

Losing the Initialization Vector in Cipher Block Chaining

Can a monk deflect thrown melee weapons?

How can players take actions together that are impossible otherwise?

Fishing simulator

How to say that you spent the night with someone, you were only sleeping and nothing else?

What computer would be fastest for Mathematica Home Edition?

Need a suitable toxic chemical for a murder plot in my novel

Unable to start mainnet node docker container

Is above average number of years spent on PhD considered a red flag in future academia or industry positions?

Biased dice probability question

How do I keep my slimes from escaping their pens?

Is there a service that would inform me whenever a new direct route is scheduled from a given airport?

How are presidential pardons supposed to be used?

Why is "Captain Marvel" translated as male in Portugal?

How to market an anarchic city as a tourism spot to people living in civilized areas?

Keep going mode for require-package

Complexity of many constant time steps with occasional logarithmic steps

Replacing HDD with SSD; what about non-APFS/APFS?

Autumning in love



Given a list of coordinates, find the rectangle with minimal area



Announcing the arrival of Valued Associate #679: Cesar Manara
Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)Std lib-like C++ function to find nearest elements in a containerFind Triangle Triplets from a list of given numbersFind non duplicateTriangle Triplets from a list of given numbersCalculating the area of a circleCalculate area and perimeter for shapes: polygon, circle, rectangle and triangle - follow upAnother way to find the nearest neighbor points in a 2D planeShifting the origin of a large list of coordinatesFinding non-self-intersecting paths of certain moves that touch all points in a gridPortability in using up-and-coming library featuresFind the first palindrome larger than the given number



.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty margin-bottom:0;








0












$begingroup$


A problem on leetcode asks the coder to write an algorithm to take a bunch of coordinates in the xy-plane and return the minimum area of a rectangle made from four of these coordinates (or return 0 if no four of these coordinates describe a rectangle). Admissible rectangles must have sides parallel to the coordinate axes.



I'd appreciate any comments and improvements on my code whatsoever. Of course some of them may not make sense in the context of Leetcode, and I mention such an example below. But they may still be good for me to be aware of. My code scores in the 96th percentile of solutions on speed, and 100th percentile on memory, so I don't expect any drastic improvements. I'm posting this code because I think it's good, and I want to get a reality check if it's actually good or not -- this is my first post on code review.



Leetcode asks the code to be a class called Solution with a method int minAreaRect(std::vector<std::vector<int>>& points), and they will test this code using this method. One effect of this is that it does no good (as far as I know) to make a constructor Solution::Solution(std::vector<std::vector<int>> &points), which would be the most natural. Therefore, for instance, I have to store points in my class as a pointer, not a reference, because I can't know what points is at construction time.



This problem seems to call for something like a multimap from x-coordinates to the set of y-coordinates for which (x,y) is in points. I chose to implement my own "flat multimap" -- since I am doing all my insertion at once, it seems better to just make a sorted vector, and so I just sorted the input vector. (The problem does not address whether I am allowed to modify the input vector -- if I were not allowed to, I would copy it and sort the copy.)



My code examines all possible pairs of distinct x-coordinates, and then looks for the overlap of the y-coordinates associated with them. If the intersection of their y-coordinates has less than two elements, there is no possible rectangle to be made from this pair of x-coordinates. Therefore the code bypasses x-coordinates that have fewer than two y-coordinates associated with them.



An example test case would look like this



int main ()

std::vector<std::vector<int>> v 0,1, 3,2, 5, 5, 4, 5, 4,4, 2,0, 2, 3, 2, 2, 1, 0, 5, 1, 2, 5, 5, 2, 2, 4, 4, 0;
Solution sol;
std::cout << sol.minAreaRect(v);
return 0;



Outputs: 2, because (2,4), (2,5), (4,4), and (4,5) describe a rectangle of area two, and that is the best we can do.



My code uses two different comparators -- one which puts coordinates in lexicographic order, and one called comp_coords_fc_only which simply compares the first coordinate. The reason I made the second is so that I could call std::upper_bound(current_coord, points.end(), (*current_coord)[0], comp_coords_fc_only), which will take me to the next entry of points that has a different x-coordinate. I put this in a method called next_fc.



#include <vector>
#include <algorithm>
#include <iterator>
#include <iostream>

using coord_it = std::vector<std::vector<int>>::iterator;

bool comp_coords_lexic(const std::vector<int> &lhs, const std::vector<int> &rhs)
if (lhs[0] != rhs[0])
return lhs[0] < rhs[0];
return lhs[1] < rhs[1];


bool comp_coords_fc_only(const std::vector<int> &lhs, const std::vector<int> &rhs)
return (lhs[0] < rhs[0]);


class Solution
//"fc" = "first coordinate" and "sc" = "second coordinate"
public:
int minAreaRect(std::vector<std::vector<int>>& _points)

if (_points.size() < 4)
return 0;

std::sort(_points.begin(), _points.end(), comp_coords_lexic);

points = &_points;
int record_min_area = INT_MAX;

for (coord_it current_left_fc = _points.begin(); current_left_fc != _points.end(); current_left_fc = next_fc(current_left_fc))
if (has_less_than_two(current_left_fc))
continue;

for (coord_it current_right_fc = next_fc(current_left_fc); current_right_fc != _points.end(); current_right_fc = next_fc(current_right_fc))
if (has_less_than_two(current_right_fc))
continue;

int distance_fc = (*current_right_fc)[0] - (*current_left_fc)[0];

if (distance_fc > record_min_area)
continue; // need not explore first coords that are so far apart the area would necessarily be too big.

int min_distance_sc = min_distance_shared_scs(current_left_fc, current_right_fc);

if (min_distance_sc == 0)
continue; // if they don't have two scs in common

record_min_area = std::min(record_min_area, distance_fc * min_distance_sc);
// for loop, right fc
// for loop, left fc

if (record_min_area == INT_MAX)
return 0;
return record_min_area;


private:
int min_distance_shared_scs(coord_it beg_left_fc_range, coord_it beg_right_fc_range)
// given two first coordinates (in the form of iterators pointing at the first entry
// with that first coordinate) x1 and x2, find min d(y1, y2) subject to (x1,y1), (x1, y2)
// (x2, y1), and (x2, y2) all being in the coordinate vector.

int last_match = INT_MIN; // sentinel value
int record_min_distance = INT_MAX;

auto upper_bound_left = next_fc(beg_left_fc_range), upper_bound_right = next_fc(beg_right_fc_range);
auto current_left_sc = beg_left_fc_range, current_right_sc = beg_right_fc_range;
while (current_left_sc != upper_bound_left && current_right_sc != upper_bound_right)

if (equal_second_coord(current_left_sc, current_right_sc))

if (last_match == INT_MIN)
last_match = (*current_left_sc)[1];
++current_left_sc; ++current_right_sc;
continue;


int distance_from_last = (*current_left_sc)[1] - last_match;
record_min_distance = std::min(record_min_distance, distance_from_last);
last_match = (*current_left_sc)[1];
++current_left_sc; ++current_right_sc;
continue;


if ((*current_left_sc)[1] < (*current_right_sc)[1])
++current_left_sc;
else
++current_right_sc;
// while loop going through two ranges

if (record_min_distance == INT_MAX)
return 0;
return record_min_distance;


static bool equal_second_coord(coord_it it1, coord_it it2)
return ((*it1)[1] == (*it2)[1]);


bool has_less_than_two(coord_it input_it)
auto upper_bound = next_fc(input_it);
return (std::distance(input_it, upper_bound) < 2);


coord_it next_fc(coord_it it)
return std::upper_bound(it, (*points).end(), *it, comp_coords_fc_only);


std::vector<std::vector<int>>* points;
;








share







New contributor




Eric Auld is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$


















    0












    $begingroup$


    A problem on leetcode asks the coder to write an algorithm to take a bunch of coordinates in the xy-plane and return the minimum area of a rectangle made from four of these coordinates (or return 0 if no four of these coordinates describe a rectangle). Admissible rectangles must have sides parallel to the coordinate axes.



    I'd appreciate any comments and improvements on my code whatsoever. Of course some of them may not make sense in the context of Leetcode, and I mention such an example below. But they may still be good for me to be aware of. My code scores in the 96th percentile of solutions on speed, and 100th percentile on memory, so I don't expect any drastic improvements. I'm posting this code because I think it's good, and I want to get a reality check if it's actually good or not -- this is my first post on code review.



    Leetcode asks the code to be a class called Solution with a method int minAreaRect(std::vector<std::vector<int>>& points), and they will test this code using this method. One effect of this is that it does no good (as far as I know) to make a constructor Solution::Solution(std::vector<std::vector<int>> &points), which would be the most natural. Therefore, for instance, I have to store points in my class as a pointer, not a reference, because I can't know what points is at construction time.



    This problem seems to call for something like a multimap from x-coordinates to the set of y-coordinates for which (x,y) is in points. I chose to implement my own "flat multimap" -- since I am doing all my insertion at once, it seems better to just make a sorted vector, and so I just sorted the input vector. (The problem does not address whether I am allowed to modify the input vector -- if I were not allowed to, I would copy it and sort the copy.)



    My code examines all possible pairs of distinct x-coordinates, and then looks for the overlap of the y-coordinates associated with them. If the intersection of their y-coordinates has less than two elements, there is no possible rectangle to be made from this pair of x-coordinates. Therefore the code bypasses x-coordinates that have fewer than two y-coordinates associated with them.



    An example test case would look like this



    int main ()

    std::vector<std::vector<int>> v 0,1, 3,2, 5, 5, 4, 5, 4,4, 2,0, 2, 3, 2, 2, 1, 0, 5, 1, 2, 5, 5, 2, 2, 4, 4, 0;
    Solution sol;
    std::cout << sol.minAreaRect(v);
    return 0;



    Outputs: 2, because (2,4), (2,5), (4,4), and (4,5) describe a rectangle of area two, and that is the best we can do.



    My code uses two different comparators -- one which puts coordinates in lexicographic order, and one called comp_coords_fc_only which simply compares the first coordinate. The reason I made the second is so that I could call std::upper_bound(current_coord, points.end(), (*current_coord)[0], comp_coords_fc_only), which will take me to the next entry of points that has a different x-coordinate. I put this in a method called next_fc.



    #include <vector>
    #include <algorithm>
    #include <iterator>
    #include <iostream>

    using coord_it = std::vector<std::vector<int>>::iterator;

    bool comp_coords_lexic(const std::vector<int> &lhs, const std::vector<int> &rhs)
    if (lhs[0] != rhs[0])
    return lhs[0] < rhs[0];
    return lhs[1] < rhs[1];


    bool comp_coords_fc_only(const std::vector<int> &lhs, const std::vector<int> &rhs)
    return (lhs[0] < rhs[0]);


    class Solution
    //"fc" = "first coordinate" and "sc" = "second coordinate"
    public:
    int minAreaRect(std::vector<std::vector<int>>& _points)

    if (_points.size() < 4)
    return 0;

    std::sort(_points.begin(), _points.end(), comp_coords_lexic);

    points = &_points;
    int record_min_area = INT_MAX;

    for (coord_it current_left_fc = _points.begin(); current_left_fc != _points.end(); current_left_fc = next_fc(current_left_fc))
    if (has_less_than_two(current_left_fc))
    continue;

    for (coord_it current_right_fc = next_fc(current_left_fc); current_right_fc != _points.end(); current_right_fc = next_fc(current_right_fc))
    if (has_less_than_two(current_right_fc))
    continue;

    int distance_fc = (*current_right_fc)[0] - (*current_left_fc)[0];

    if (distance_fc > record_min_area)
    continue; // need not explore first coords that are so far apart the area would necessarily be too big.

    int min_distance_sc = min_distance_shared_scs(current_left_fc, current_right_fc);

    if (min_distance_sc == 0)
    continue; // if they don't have two scs in common

    record_min_area = std::min(record_min_area, distance_fc * min_distance_sc);
    // for loop, right fc
    // for loop, left fc

    if (record_min_area == INT_MAX)
    return 0;
    return record_min_area;


    private:
    int min_distance_shared_scs(coord_it beg_left_fc_range, coord_it beg_right_fc_range)
    // given two first coordinates (in the form of iterators pointing at the first entry
    // with that first coordinate) x1 and x2, find min d(y1, y2) subject to (x1,y1), (x1, y2)
    // (x2, y1), and (x2, y2) all being in the coordinate vector.

    int last_match = INT_MIN; // sentinel value
    int record_min_distance = INT_MAX;

    auto upper_bound_left = next_fc(beg_left_fc_range), upper_bound_right = next_fc(beg_right_fc_range);
    auto current_left_sc = beg_left_fc_range, current_right_sc = beg_right_fc_range;
    while (current_left_sc != upper_bound_left && current_right_sc != upper_bound_right)

    if (equal_second_coord(current_left_sc, current_right_sc))

    if (last_match == INT_MIN)
    last_match = (*current_left_sc)[1];
    ++current_left_sc; ++current_right_sc;
    continue;


    int distance_from_last = (*current_left_sc)[1] - last_match;
    record_min_distance = std::min(record_min_distance, distance_from_last);
    last_match = (*current_left_sc)[1];
    ++current_left_sc; ++current_right_sc;
    continue;


    if ((*current_left_sc)[1] < (*current_right_sc)[1])
    ++current_left_sc;
    else
    ++current_right_sc;
    // while loop going through two ranges

    if (record_min_distance == INT_MAX)
    return 0;
    return record_min_distance;


    static bool equal_second_coord(coord_it it1, coord_it it2)
    return ((*it1)[1] == (*it2)[1]);


    bool has_less_than_two(coord_it input_it)
    auto upper_bound = next_fc(input_it);
    return (std::distance(input_it, upper_bound) < 2);


    coord_it next_fc(coord_it it)
    return std::upper_bound(it, (*points).end(), *it, comp_coords_fc_only);


    std::vector<std::vector<int>>* points;
    ;








    share







    New contributor




    Eric Auld is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.







    $endgroup$














      0












      0








      0





      $begingroup$


      A problem on leetcode asks the coder to write an algorithm to take a bunch of coordinates in the xy-plane and return the minimum area of a rectangle made from four of these coordinates (or return 0 if no four of these coordinates describe a rectangle). Admissible rectangles must have sides parallel to the coordinate axes.



      I'd appreciate any comments and improvements on my code whatsoever. Of course some of them may not make sense in the context of Leetcode, and I mention such an example below. But they may still be good for me to be aware of. My code scores in the 96th percentile of solutions on speed, and 100th percentile on memory, so I don't expect any drastic improvements. I'm posting this code because I think it's good, and I want to get a reality check if it's actually good or not -- this is my first post on code review.



      Leetcode asks the code to be a class called Solution with a method int minAreaRect(std::vector<std::vector<int>>& points), and they will test this code using this method. One effect of this is that it does no good (as far as I know) to make a constructor Solution::Solution(std::vector<std::vector<int>> &points), which would be the most natural. Therefore, for instance, I have to store points in my class as a pointer, not a reference, because I can't know what points is at construction time.



      This problem seems to call for something like a multimap from x-coordinates to the set of y-coordinates for which (x,y) is in points. I chose to implement my own "flat multimap" -- since I am doing all my insertion at once, it seems better to just make a sorted vector, and so I just sorted the input vector. (The problem does not address whether I am allowed to modify the input vector -- if I were not allowed to, I would copy it and sort the copy.)



      My code examines all possible pairs of distinct x-coordinates, and then looks for the overlap of the y-coordinates associated with them. If the intersection of their y-coordinates has less than two elements, there is no possible rectangle to be made from this pair of x-coordinates. Therefore the code bypasses x-coordinates that have fewer than two y-coordinates associated with them.



      An example test case would look like this



      int main ()

      std::vector<std::vector<int>> v 0,1, 3,2, 5, 5, 4, 5, 4,4, 2,0, 2, 3, 2, 2, 1, 0, 5, 1, 2, 5, 5, 2, 2, 4, 4, 0;
      Solution sol;
      std::cout << sol.minAreaRect(v);
      return 0;



      Outputs: 2, because (2,4), (2,5), (4,4), and (4,5) describe a rectangle of area two, and that is the best we can do.



      My code uses two different comparators -- one which puts coordinates in lexicographic order, and one called comp_coords_fc_only which simply compares the first coordinate. The reason I made the second is so that I could call std::upper_bound(current_coord, points.end(), (*current_coord)[0], comp_coords_fc_only), which will take me to the next entry of points that has a different x-coordinate. I put this in a method called next_fc.



      #include <vector>
      #include <algorithm>
      #include <iterator>
      #include <iostream>

      using coord_it = std::vector<std::vector<int>>::iterator;

      bool comp_coords_lexic(const std::vector<int> &lhs, const std::vector<int> &rhs)
      if (lhs[0] != rhs[0])
      return lhs[0] < rhs[0];
      return lhs[1] < rhs[1];


      bool comp_coords_fc_only(const std::vector<int> &lhs, const std::vector<int> &rhs)
      return (lhs[0] < rhs[0]);


      class Solution
      //"fc" = "first coordinate" and "sc" = "second coordinate"
      public:
      int minAreaRect(std::vector<std::vector<int>>& _points)

      if (_points.size() < 4)
      return 0;

      std::sort(_points.begin(), _points.end(), comp_coords_lexic);

      points = &_points;
      int record_min_area = INT_MAX;

      for (coord_it current_left_fc = _points.begin(); current_left_fc != _points.end(); current_left_fc = next_fc(current_left_fc))
      if (has_less_than_two(current_left_fc))
      continue;

      for (coord_it current_right_fc = next_fc(current_left_fc); current_right_fc != _points.end(); current_right_fc = next_fc(current_right_fc))
      if (has_less_than_two(current_right_fc))
      continue;

      int distance_fc = (*current_right_fc)[0] - (*current_left_fc)[0];

      if (distance_fc > record_min_area)
      continue; // need not explore first coords that are so far apart the area would necessarily be too big.

      int min_distance_sc = min_distance_shared_scs(current_left_fc, current_right_fc);

      if (min_distance_sc == 0)
      continue; // if they don't have two scs in common

      record_min_area = std::min(record_min_area, distance_fc * min_distance_sc);
      // for loop, right fc
      // for loop, left fc

      if (record_min_area == INT_MAX)
      return 0;
      return record_min_area;


      private:
      int min_distance_shared_scs(coord_it beg_left_fc_range, coord_it beg_right_fc_range)
      // given two first coordinates (in the form of iterators pointing at the first entry
      // with that first coordinate) x1 and x2, find min d(y1, y2) subject to (x1,y1), (x1, y2)
      // (x2, y1), and (x2, y2) all being in the coordinate vector.

      int last_match = INT_MIN; // sentinel value
      int record_min_distance = INT_MAX;

      auto upper_bound_left = next_fc(beg_left_fc_range), upper_bound_right = next_fc(beg_right_fc_range);
      auto current_left_sc = beg_left_fc_range, current_right_sc = beg_right_fc_range;
      while (current_left_sc != upper_bound_left && current_right_sc != upper_bound_right)

      if (equal_second_coord(current_left_sc, current_right_sc))

      if (last_match == INT_MIN)
      last_match = (*current_left_sc)[1];
      ++current_left_sc; ++current_right_sc;
      continue;


      int distance_from_last = (*current_left_sc)[1] - last_match;
      record_min_distance = std::min(record_min_distance, distance_from_last);
      last_match = (*current_left_sc)[1];
      ++current_left_sc; ++current_right_sc;
      continue;


      if ((*current_left_sc)[1] < (*current_right_sc)[1])
      ++current_left_sc;
      else
      ++current_right_sc;
      // while loop going through two ranges

      if (record_min_distance == INT_MAX)
      return 0;
      return record_min_distance;


      static bool equal_second_coord(coord_it it1, coord_it it2)
      return ((*it1)[1] == (*it2)[1]);


      bool has_less_than_two(coord_it input_it)
      auto upper_bound = next_fc(input_it);
      return (std::distance(input_it, upper_bound) < 2);


      coord_it next_fc(coord_it it)
      return std::upper_bound(it, (*points).end(), *it, comp_coords_fc_only);


      std::vector<std::vector<int>>* points;
      ;








      share







      New contributor




      Eric Auld is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.







      $endgroup$




      A problem on leetcode asks the coder to write an algorithm to take a bunch of coordinates in the xy-plane and return the minimum area of a rectangle made from four of these coordinates (or return 0 if no four of these coordinates describe a rectangle). Admissible rectangles must have sides parallel to the coordinate axes.



      I'd appreciate any comments and improvements on my code whatsoever. Of course some of them may not make sense in the context of Leetcode, and I mention such an example below. But they may still be good for me to be aware of. My code scores in the 96th percentile of solutions on speed, and 100th percentile on memory, so I don't expect any drastic improvements. I'm posting this code because I think it's good, and I want to get a reality check if it's actually good or not -- this is my first post on code review.



      Leetcode asks the code to be a class called Solution with a method int minAreaRect(std::vector<std::vector<int>>& points), and they will test this code using this method. One effect of this is that it does no good (as far as I know) to make a constructor Solution::Solution(std::vector<std::vector<int>> &points), which would be the most natural. Therefore, for instance, I have to store points in my class as a pointer, not a reference, because I can't know what points is at construction time.



      This problem seems to call for something like a multimap from x-coordinates to the set of y-coordinates for which (x,y) is in points. I chose to implement my own "flat multimap" -- since I am doing all my insertion at once, it seems better to just make a sorted vector, and so I just sorted the input vector. (The problem does not address whether I am allowed to modify the input vector -- if I were not allowed to, I would copy it and sort the copy.)



      My code examines all possible pairs of distinct x-coordinates, and then looks for the overlap of the y-coordinates associated with them. If the intersection of their y-coordinates has less than two elements, there is no possible rectangle to be made from this pair of x-coordinates. Therefore the code bypasses x-coordinates that have fewer than two y-coordinates associated with them.



      An example test case would look like this



      int main ()

      std::vector<std::vector<int>> v 0,1, 3,2, 5, 5, 4, 5, 4,4, 2,0, 2, 3, 2, 2, 1, 0, 5, 1, 2, 5, 5, 2, 2, 4, 4, 0;
      Solution sol;
      std::cout << sol.minAreaRect(v);
      return 0;



      Outputs: 2, because (2,4), (2,5), (4,4), and (4,5) describe a rectangle of area two, and that is the best we can do.



      My code uses two different comparators -- one which puts coordinates in lexicographic order, and one called comp_coords_fc_only which simply compares the first coordinate. The reason I made the second is so that I could call std::upper_bound(current_coord, points.end(), (*current_coord)[0], comp_coords_fc_only), which will take me to the next entry of points that has a different x-coordinate. I put this in a method called next_fc.



      #include <vector>
      #include <algorithm>
      #include <iterator>
      #include <iostream>

      using coord_it = std::vector<std::vector<int>>::iterator;

      bool comp_coords_lexic(const std::vector<int> &lhs, const std::vector<int> &rhs)
      if (lhs[0] != rhs[0])
      return lhs[0] < rhs[0];
      return lhs[1] < rhs[1];


      bool comp_coords_fc_only(const std::vector<int> &lhs, const std::vector<int> &rhs)
      return (lhs[0] < rhs[0]);


      class Solution
      //"fc" = "first coordinate" and "sc" = "second coordinate"
      public:
      int minAreaRect(std::vector<std::vector<int>>& _points)

      if (_points.size() < 4)
      return 0;

      std::sort(_points.begin(), _points.end(), comp_coords_lexic);

      points = &_points;
      int record_min_area = INT_MAX;

      for (coord_it current_left_fc = _points.begin(); current_left_fc != _points.end(); current_left_fc = next_fc(current_left_fc))
      if (has_less_than_two(current_left_fc))
      continue;

      for (coord_it current_right_fc = next_fc(current_left_fc); current_right_fc != _points.end(); current_right_fc = next_fc(current_right_fc))
      if (has_less_than_two(current_right_fc))
      continue;

      int distance_fc = (*current_right_fc)[0] - (*current_left_fc)[0];

      if (distance_fc > record_min_area)
      continue; // need not explore first coords that are so far apart the area would necessarily be too big.

      int min_distance_sc = min_distance_shared_scs(current_left_fc, current_right_fc);

      if (min_distance_sc == 0)
      continue; // if they don't have two scs in common

      record_min_area = std::min(record_min_area, distance_fc * min_distance_sc);
      // for loop, right fc
      // for loop, left fc

      if (record_min_area == INT_MAX)
      return 0;
      return record_min_area;


      private:
      int min_distance_shared_scs(coord_it beg_left_fc_range, coord_it beg_right_fc_range)
      // given two first coordinates (in the form of iterators pointing at the first entry
      // with that first coordinate) x1 and x2, find min d(y1, y2) subject to (x1,y1), (x1, y2)
      // (x2, y1), and (x2, y2) all being in the coordinate vector.

      int last_match = INT_MIN; // sentinel value
      int record_min_distance = INT_MAX;

      auto upper_bound_left = next_fc(beg_left_fc_range), upper_bound_right = next_fc(beg_right_fc_range);
      auto current_left_sc = beg_left_fc_range, current_right_sc = beg_right_fc_range;
      while (current_left_sc != upper_bound_left && current_right_sc != upper_bound_right)

      if (equal_second_coord(current_left_sc, current_right_sc))

      if (last_match == INT_MIN)
      last_match = (*current_left_sc)[1];
      ++current_left_sc; ++current_right_sc;
      continue;


      int distance_from_last = (*current_left_sc)[1] - last_match;
      record_min_distance = std::min(record_min_distance, distance_from_last);
      last_match = (*current_left_sc)[1];
      ++current_left_sc; ++current_right_sc;
      continue;


      if ((*current_left_sc)[1] < (*current_right_sc)[1])
      ++current_left_sc;
      else
      ++current_right_sc;
      // while loop going through two ranges

      if (record_min_distance == INT_MAX)
      return 0;
      return record_min_distance;


      static bool equal_second_coord(coord_it it1, coord_it it2)
      return ((*it1)[1] == (*it2)[1]);


      bool has_less_than_two(coord_it input_it)
      auto upper_bound = next_fc(input_it);
      return (std::distance(input_it, upper_bound) < 2);


      coord_it next_fc(coord_it it)
      return std::upper_bound(it, (*points).end(), *it, comp_coords_fc_only);


      std::vector<std::vector<int>>* points;
      ;






      c++





      share







      New contributor




      Eric Auld is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.










      share







      New contributor




      Eric Auld is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.








      share



      share






      New contributor




      Eric Auld is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.









      asked 1 min ago









      Eric AuldEric Auld

      1011




      1011




      New contributor




      Eric Auld is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.





      New contributor





      Eric Auld is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.






      Eric Auld is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.




















          0






          active

          oldest

          votes












          Your Answer






          StackExchange.ifUsing("editor", function ()
          StackExchange.using("externalEditor", function ()
          StackExchange.using("snippets", function ()
          StackExchange.snippets.init();
          );
          );
          , "code-snippets");

          StackExchange.ready(function()
          var channelOptions =
          tags: "".split(" "),
          id: "196"
          ;
          initTagRenderer("".split(" "), "".split(" "), channelOptions);

          StackExchange.using("externalEditor", function()
          // Have to fire editor after snippets, if snippets enabled
          if (StackExchange.settings.snippets.snippetsEnabled)
          StackExchange.using("snippets", function()
          createEditor();
          );

          else
          createEditor();

          );

          function createEditor()
          StackExchange.prepareEditor(
          heartbeatType: 'answer',
          autoActivateHeartbeat: false,
          convertImagesToLinks: false,
          noModals: true,
          showLowRepImageUploadWarning: true,
          reputationToPostImages: null,
          bindNavPrevention: true,
          postfix: "",
          imageUploader:
          brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
          contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
          allowUrls: true
          ,
          onDemand: true,
          discardSelector: ".discard-answer"
          ,immediatelyShowMarkdownHelp:true
          );



          );






          Eric Auld is a new contributor. Be nice, and check out our Code of Conduct.









          draft saved

          draft discarded


















          StackExchange.ready(
          function ()
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f217465%2fgiven-a-list-of-coordinates-find-the-rectangle-with-minimal-area%23new-answer', 'question_page');

          );

          Post as a guest















          Required, but never shown

























          0






          active

          oldest

          votes








          0






          active

          oldest

          votes









          active

          oldest

          votes






          active

          oldest

          votes








          Eric Auld is a new contributor. Be nice, and check out our Code of Conduct.









          draft saved

          draft discarded


















          Eric Auld is a new contributor. Be nice, and check out our Code of Conduct.












          Eric Auld is a new contributor. Be nice, and check out our Code of Conduct.











          Eric Auld is a new contributor. Be nice, and check out our Code of Conduct.














          Thanks for contributing an answer to Code Review Stack Exchange!


          • Please be sure to answer the question. Provide details and share your research!

          But avoid


          • Asking for help, clarification, or responding to other answers.

          • Making statements based on opinion; back them up with references or personal experience.

          Use MathJax to format equations. MathJax reference.


          To learn more, see our tips on writing great answers.




          draft saved


          draft discarded














          StackExchange.ready(
          function ()
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f217465%2fgiven-a-list-of-coordinates-find-the-rectangle-with-minimal-area%23new-answer', 'question_page');

          );

          Post as a guest















          Required, but never shown





















































          Required, but never shown














          Required, but never shown












          Required, but never shown







          Required, but never shown

































          Required, but never shown














          Required, but never shown












          Required, but never shown







          Required, but never shown







          Popular posts from this blog

          名間水力發電廠 目录 沿革 設施 鄰近設施 註釋 外部連結 导航菜单23°50′10″N 120°42′41″E / 23.83611°N 120.71139°E / 23.83611; 120.7113923°50′10″N 120°42′41″E / 23.83611°N 120.71139°E / 23.83611; 120.71139計畫概要原始内容臺灣第一座BOT 模式開發的水力發電廠-名間水力電廠名間水力發電廠 水利署首件BOT案原始内容《小檔案》名間電廠 首座BOT水力發電廠原始内容名間電廠BOT - 經濟部水利署中區水資源局

          Prove that NP is closed under karp reduction?Space(n) not closed under Karp reductions - what about NTime(n)?Class P is closed under rotation?Prove or disprove that $NL$ is closed under polynomial many-one reductions$mathbfNC_2$ is closed under log-space reductionOn Karp reductionwhen can I know if a class (complexity) is closed under reduction (cook/karp)Check if class $PSPACE$ is closed under polyonomially space reductionIs NPSPACE also closed under polynomial-time reduction and under log-space reduction?Prove PSPACE is closed under complement?Prove PSPACE is closed under union?

          Is my guitar’s action too high? Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 23, 2019 at 23:30 UTC (7:30pm US/Eastern)Strings too stiff on a recently purchased acoustic guitar | Cort AD880CEIs the action of my guitar really high?Μy little finger is too weak to play guitarWith guitar, how long should I give my fingers to strengthen / callous?When playing a fret the guitar sounds mutedPlaying (Barre) chords up the guitar neckI think my guitar strings are wound too tight and I can't play barre chordsF barre chord on an SG guitarHow to find to the right strings of a barre chord by feel?High action on higher fret on my steel acoustic guitar