HoleCakeCuts
SRM 411 · 2008-07-24 · by hken
SRM 411 · 2008-07-24 · by hken · Geometry, Simple Math
Problem Statement
Problem Statement
Little Bonnie has been given a special cake as a reward for her good performance in her Math class. When viewed from above, the cake is a square, with an empty square hole inside. Both squares are centered at (0, 0) and their sides are parallel to the x- and y-axes.
Bonnie is going to cut the cake using several horizontal and vertical cuts. These cuts are given in theint[] s horizontalCuts and verticalCuts. The i-th horizontal cut is a line parallel to the x-axis which goes through the point (0, horizontalCuts[i]). Likewise, the i-th vertical cut is a line parallel to the y-axis which goes through the point (verticalCuts[i], 0). All cuts have infinite lengths.
You are given anint cakeLength, half of the side length of the outer square, and an int holeLength, half of the side length of the inner square hole. Note that both of these numbers are halves of the sides of the corresponding squares. Return the number of pieces of cake that will exist after all the cuts are performed.
Bonnie is going to cut the cake using several horizontal and vertical cuts. These cuts are given in the
You are given an
Notes
- A piece is a region of the cake with non-zero area.
Constraints
- cakeLength will be between 2 and 100, inclusive.
- holeLength will be between 1 and (cakeLength-1), inclusive.
- horizontalCuts and verticalCuts will each contain between 0 and 50 elements, inclusive.
- Each element of horizontalCuts and verticalCuts will be between (-cakeLength+1) and (cakeLength-1), inclusive.
- Elements of horizontalCuts will be distinct.
- Elements of verticalCuts will be distinct.
Examples
0)
5
3
{1, -4}
{1}
Returns: 6
The cake has the side length of 10, and the side of the hole is 6. Two horizontal and one vertical cuts divide the cake into 6 pieces. Those pieces are colored differently in the following picture:
1)
10
5
{}
{-2, 2}
Returns: 4
There may be no horizontal cuts.
2)
10
5
{1}
{-5, 5}
Returns: 6
3)
10
5
{}
{-7, 7}
Returns: 3
4)
10
5
{}
{7}
Returns: 2
Submissions are judged against all 254 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class HoleCakeCuts with a public method int cutTheCake(int cakeLength, int holeLength, vector<int> horizontalCuts, vector<int> verticalCuts) · 254 test cases · 2 s / 256 MB per case