Rectangle After Sequential Cuts
National Olympiad — Regional round (2024 season)
Submission name: rectcut.cpp
Problem summary
Perform horizontal and vertical cuts, discarding the named side after each cut. Find the remaining area.
Input
x1 y1 x2 y2, cut count N, then H/V coordinate L/R/T/B for each cut.
Output
The final rectangle area.
Constraints
0≤N≤20; initial coordinates lie in [0,10^9]; 0<cut coordinate<10^9. Each cut crosses the current rectangle.
Worked example
Input and output for the worked example discussed below.
Input
1 2 20 30 2 V 3 L H 20 T
Output
306
Solution analysis
- After each axis-aligned cut, the surviving shape remains a rectangle. Four boundary coordinates are therefore sufficient state.
- Removing L sets the left bound, R the right bound, B the bottom bound, and T the top bound to the cut coordinate. The letter names what is removed.
- The sample first leaves x in [3,20], then y in [2,20], giving (20−3)(20−2)=306. No-cut input leaves the original area unchanged.
Why it works
Each operation replaces exactly the boundary next to the removed side. Induction shows that the maintained bounds describe the final rectangle, whose width times height is its area.
Watch out. Use long long because areas reach 10^18. Do not reverse removed and retained sides.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
using namespace std;
int main(){
long long left;
long long bottom;
long long right;
long long top;
cin>>left>>bottom>>right>>top;
int cuts;
cin>>cuts;
while(cuts-->0){
char direction;
char removed;
long long position;
cin>>direction>>position>>removed;
// One cut replaces exactly one boundary.
if(removed=='L'){
left=position;
}
else if(removed=='R'){
right=position;
}
else if(removed=='B'){
bottom=position;
}
else{
top=position;
}
}
cout<<(right-left)*(top-bottom)<<'\n';
}