I use ternary search but the problem is that they are some invalid values in range [0:k] or in f(x), How can i deal with these invalid values?
This is the problem: 102881B - Anany in the Army
My steps:
I will brute force in value where i will make ternary search on each value of a, b, c then take the max area. The problem is when i add value from range [0:k] to any side, This may result that the triangle isn't right.
This is my Code:
long double f(long double a, long double b, long double c){
if((a + b) <= c || (a + c) <= b || (b + c) <= a) return NINF;
long double s = ((a + b + c) / 2);
return sqrt(s * (s - a) * (s - b) * (s - c));
}
long double ts(long double a, long double b, long double c, long double k){
long double l = 0, r = k;
long double maxVal = 0;
while(r - l > 1e-9){
long double mid = ((l + r) / 2);
if(f(a + mid, b, c) < f(a + mid + 1e-7, b, c)){
l = mid;
}else{
r = mid;
}
}
return f(a + r, b, c);
}
void solve(){
long double a, b, c, k;
read(a, b, c, k);
cout << setprecision(10) << max({ts(a, b, c, k), ts(b, a, c, k), ts(c, a, b, k)}) << "\n";
}
Why're you ternary searching? The values are up to 10^4, so I think you can just brute-force the value that you'll add to a stick(also brute-force on which stick you'll add it to) and then just check if the 3 sides satisfy the triangle inequality, if it does then just simply apply Heron's Formula.
Also the values of x that if you add to a particular stick makes a valid triangle would always be in a range [l, r] where l and r are not necessarily positive.
Yes, the values are up 10^4 but i don't have only integers but also all real numbers in this range so, i can't brute force on values.
As the other sides are also only integers, so I think iterating on integer values only would work. But if you have a way to ternary search and the only problem is that some values of k might be invalid then consider this:
First find that range and then ternary search in that range.
Thx
Hi, I tried the problem, please bound the range l-r to the triangle inequality and ternary search works.
328404154
Thanks! Once I bounded the range, it got accepted. However, there was a problem that I didn’t understand. When I wanted to get an accurate floating-point number, using while(r — l < 1e-9) gave the wrong result, but using for(int i = 0; i < 200; i++) got accepted.
Stop making comments to yourself and then deleting them to make your blog appear at the top.
I swear I'm not the one who does that