# ICM0004 (Stack Of Rectangles) - Editorial

Div-1 Contest

Div-2 Contest

Div-3 Contest

Author: dyrroth

Tester: catastrophic25

Editorialist: dyrroth

EASY-MEDIUM

# PREREQUISITES:

Maths, Geometry and Good observation skills

# PROBLEM:

Given a triangle with side lengths a, b and c, you have to choose one of the sides as the base of the triangle and stack k rectangles on top of one another parallel to the base of the triangle. These rectangles can have any dimensions, but they must lie inside the triangle and no two rectangles can intersect.

Your task is to find the maximum possible value of the sum of areas of the rectangles.

# EXPLANATION:

### Observation :

By simple observation we can see that sum of areas will be maximum when height of all the k rectangles are equal to h/(k+1).

And the answer comes out to be k/(k+1)*(area of traingle).

### Proof :

Stack of Rectangles - Proof

# TIME COMPLEXITY

The time complexity is O(log(N)) per test case.

The memory complexity is O(1) per test case.

# SOLUTIONS

Setter and Editorialist's Solution
``````#include<bits/stdc++.h>
using namespace std;
int main(){
int T=1;
cin>>T;
while(T--){
long double a,b,c,k;
cin>>a>>b>>c>>k;
long double s=(a+b+c)/2;
long double area=sqrt(s * (s-a) * (s-b) * (s-c));
long double ans = (area * k)/(k+1) ;
cout<<fixed<<setprecision(9)<<ans<<"\n";
}
return 0;
}
/*_*/
``````
Tester's Solution
``````#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double

int main(){
int t;
cin >>t;
while(t--){
ll a,b,c;
cin >>a >> b >> c;
int k ;
cin >> k;
ld s = (a + b + c)/(2.0);
ld area = sqrt(s * (s - a) * (s - b) * (s - c));
ld ans = (k/((k + 1) * 1.0)) * area;
cout << fixed << setprecision(9) << ans << endl;
}
}
``````

Is there any other way to solve this problem?