Integer-Sided Rectangles
Autumn Tournament (2009)
Submission name: rect.cpp
Problem summary
For a given positive area s, count rectangles with positive integer side lengths, considering rotations identical. Also find their smallest perimeter.
Input
One integer s.
Output
The number of distinct rectangles and the minimum perimeter.
Constraints
1 ≤ s ≤ 100000.
Worked example
Original statement sample.
Input
36
Output
5 24
Solution analysis
- Write the shorter side as side. The longer side must be s/side, so side is valid exactly when it divides s. To avoid counting a rotated rectangle twice, consider only side ≤ s/side.
- For each divisor in that range, increment the rectangle count and evaluate 2 × (side+s/side). Keep the minimum perimeter. The loop condition side ≤ s/side avoids an unnecessary multiplication.
- Area 36 has side pairs (1,36), (2,18), (3,12), (4,9), and (6,6). There are five rectangles; the 6 by 6 square has perimeter 24.
Why it works
Every integer-sided rectangle of area s has exactly one ordered pair with shorter side first. The divisor scan enumerates each such pair once, including a square once. Taking the smallest of their actual perimeters gives the required minimum.
Watch out. Rotations are not new rectangles. Include side=√s for perfect squares. Do not count all divisors as distinct rectangles.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
using namespace std;
int main(){
int area;
cin>>area;
int count=0;
int minimumPerimeter=2*(area+1);
for(int side=1;side<=area/side;side++){
if(area%side==0){
count++;
// Each divisor gives one pair with the shorter side first.
int perimeter=2*(side+area/side);
minimumPerimeter=min(minimumPerimeter,perimeter);
}
}
cout<<count<<' '<<minimumPerimeter<<'\n';
}