BoundingBox

SRM 607 · 2013-12-22 · by Wheeler

SRM 607 · 2013-12-22 · by Wheeler · Simple Search, Iteration

Show categories

Class Name: BoundingBox

Return Type: int

Method Name: smallestArea

Arg Types: (vector<int>, vector<int>)

Problem Statement

Andrew drew a bunch of points on a sheet of graph paper. You are given the coordinates of these points in two int[]s: X and Y. That is, for each valid i, there is a point at the coordinates (X[i], Y[i]).

Now Andrew wants to draw a rectangle. The sides of the rectangle must be parallel to the coordinate axes. (In other words, each side of the rectangle must be either horizontal or vertical.) Additionally, each of Andrew's points must be inside the rectangle or on its boundary.

Return the area of the smallest possible rectangle Andrew can draw.

Constraints

X will have between 2 and 50 elements, inclusive.
X and Y will have the same number of elements.
Each element of X and Y will be between -100 and 100, inclusive.
The points described by X and Y will not be in a straight line horizontally or vertically. That is, the smallest rectangle will have a positive area.

Examples

{0,1}
{1,0}
Returns: 1

{0,-2,-1}
{-1,-1,-2}
Returns: 2

{0,0,1,0,-1,2}
{0,1,2,-2,0,-1}
Returns: 12

{9,-88,-40,98,-55,41,-38}
{-65,56,-67,7,-58,33,68}
Returns: 25110

{-56,-67,3,25,25,-21,-36,-38,34,84,4,-85}
{-80,61,-1,-20,-35,4,-65,10,22,-54,-28,75}
Returns: 26195

Submissions are judged against all 75 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class BoundingBox with a public method int smallestArea(vector<int> X, vector<int> Y) · 75 test cases · 2 s / 256 MB per case