HiddenSquares
SRM 331 · 2006-12-21 · by slex
Problem Statement
Little Greg got a set of pencils for Christmas. Since then, he has been spending hours drawing rectangles on a piece of paper. In this problem, the paper will be represented as an x-y plane. All the rectangles have sides parallel to the axes, and some of them may intersect, creating even more rectangles. Greg wonders how many squares (rectangles with sides of equal length) exist in his drawing.
For example, in the image below, Greg has drawn three rectangles, one in red, one in green, and one in blue. These three rectangles intersect to form a total of 36 rectangles, 14 of which are squares (nine 1 x 1, four 2 x 2, and one 3 x 3).
You are given the rectangles drawn by Greg in the
Constraints
- x1, y1, x2, and y2 will each contain between 1 and 50 elements, inclusive.
- x1, y1, x2, and y2 will each contain the same number of elements.
- Each element of x1, y1, x2, and y2 will be between 0 and 1000000000, inclusive.
- For all i, x1[i] will be less than x2[i], and y1[i] will be less than y2[i].
{0,1,0}
{0,0,1}
{3,2,3}
{3,3,2}
Returns: 14
The example from the problem statement.
{0,2}
{0,0}
{2,4}
{4,4}
Returns: 1
These two rectangles combine to form a single square.
{0,0,3}
{0,3,0}
{1,4,4}
{3,4,3}
Returns: 0
There are no squares here.
{453453463,453453500,453453495,453453512,453453478,453453489,
453453466,453453500,453453498,453453510,453453472,453453512,
453453519,453453514,453453521,453453518,453453523,453453517,
453453466,453453525,453453496,453453495,453453463,453453461,
453453460,453453522,453453471,453453468,453453479,453453517,
453453485,453453518,453453499,453453464,453453494}
{364646438,364646402,364646449,364646438,364646415,364646401,
364646446,364646416,364646456,364646414,364646463,364646407,
364646436,364646450,364646421,364646411,364646414,364646419,
364646445,364646427,364646405,364646442,364646418,364646464,
364646457,364646463,364646432,364646426,364646444,364646431,
364646450,364646418,364646434,364646458,364646402}
{453453488,453453510,453453525,453453523,453453493,453453500,
453453470,453453511,453453499,453453521,453453518,453453524,
453453523,453453523,453453524,453453523,453453525,453453519,
453453473,453453526,453453511,453453517,453453470,453453464,
453453511,453453524,453453516,453453516,453453492,453453524,
453453513,453453522,453453520,453453505,453453512}
{364646460,364646454,364646462,364646466,364646464,364646455,
364646457,364646461,364646457,364646450,364646466,364646453,
364646441,364646451,364646460,364646461,364646446,364646464,
364646447,364646460,364646454,364646450,364646444,364646466,
364646458,364646466,364646455,364646442,364646462,364646435,
364646464,364646444,364646455,364646459,364646430}
Returns: 124
{0,0,3,0}
{0,3,0,0}
{1,4,4,4}
{4,4,4,1}
Returns: 10
Submissions are judged against all 42 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class HiddenSquares with a public method int count(vector<int> x1, vector<int> y1, vector<int> x2, vector<int> y2) · 42 test cases · 2 s / 256 MB per case