PROBLEM LINK:
Author: dyrroth
Tester: catastrophic25
Editorialist: dyrroth
DIFFICULTY:
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 :
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;
}
}