Count Places for a New Notice
National Olympiad — Regional round (2012 season)
Submission name: notice.cpp
Problem summary
A board already holds axis-aligned rectangular notices. Count integer-coordinate top-left positions where a new U-by-W notice fits completely inside without overlapping any occupied interior.
Input
L H, then N, N rows x y width height, then U W. Coordinates start at the board’s top-left and y increases downward.
Output
The number of valid positions; 0 if none.
Constraints
10 ≤ L ≤ 120; 8 ≤ H ≤ 80; 0 ≤ N ≤ 16; notice dimensions fit within board bounds.
Worked example
Input and output for the worked example discussed below.
Input
12 8 2 2 0 3 3 6 1 5 4 2 4
Output
13
Solution analysis
- Treat each square centimetre as one grid cell. A notice with top-left (x,y), width a and height b occupies cells x…x+a−1 and y…y+b−1. Mark the union of existing notices; shared borders do not occupy another cell.
- Build a two-dimensional prefix sum of the occupied-cell grid. Inclusion-exclusion then gives the number of occupied cells inside any proposed rectangle in constant time.
- Enumerate every x from 0 through L−U and y from 0 through H−W. A candidate is valid exactly when its occupied-cell sum is zero. The new notice is not rotated: U stays horizontal and W stays vertical.
- For the 12-by-8 sample with a 2-by-4 notice, 13 top-left positions have a zero occupied-cell sum. In an empty board the same loop would count (L−U+1)(H−W+1) positions.
Why it works
The integer cell model exactly describes overlap of integer-coordinate axis-aligned rectangles. Prefix inclusion-exclusion counts the occupied cells in each candidate, so zero is equivalent to no overlap. The endpoint loops enumerate every in-bounds top-left coordinate once.
Watch out. Use half-open occupied ranges so touching edges remain legal. Include candidates touching the board’s far right or bottom. Do not add rotated placements.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
using namespace std;
int main(){
int width;
int height;
int count;
cin>>width>>height>>count;
vector<vector<int>>occupied(height+1,vector<int>(width+1));
for(int i=0;i<count;i++){
int x;
int y;
int a;
int b;
cin>>x>>y>>a>>b;
for(int row=y;row<y+b;row++){
for(int column=x;column<x+a;column++){
occupied[row+1][column+1]=1;
}
}
}
for(int row=1;row<=height;row++){
for(int column=1;column<=width;column++){
occupied[row][column]+=
occupied[row-1][column]+occupied[row][column-1]-occupied[row-1][column-1];
}
}
int u;
int w;
cin>>u>>w;
int answer=0;
for(int y=0;y+w<=height;y++){
for(int x=0;x+u<=width;x++){
// Inclusion-exclusion counts occupied cells in this candidate.
int cells=occupied[y+w][x+u]-occupied[y][x+u]-occupied[y+w][x]+occupied[y][x];
answer+=cells==0;
}
}
cout<<answer<<'\n';
}