11579 - Triangle Trouble

[f74956227]

Could someone help me with the problem? i got WA many times...
My algorithm is to sort the sides in increasing order and using heron's formula to calculate the area.
I think there can be precise error and overflow, so i use long double, is anything wrong?? Please help me

Code: Select all

Deleted after AC

[Jan]

The identifier for long double is '%Lf'.

[f74956227]

After i change the signal to %Lf, i still got WA...

[Jan]

Spoiler:


Read the problem again. The sides can be too long. So, rewrite the equation as

sqrt ( s * (s-a) * (s-b) * (s*c) ) = sqrt(s) * sqrt(s-a) * sqrt(s-b) * sqrt(s-c)
The left part contains long multiplications, so, fractional problems can occur easily. So, use the right part


Hope it helps.

[tryit1]

i got AC on this problem but i missed the insight using the sort and checking the triplets for validity area.
Can you tell me why this is true ? I could figure out that with a fixed base, the area of triangle is maximum when the other 2 sides are almost equal to each other. I reasoned it as follows

let a<b<c. Now a is very small but b and c are large. increasing a would increase the height of the triangle hence area until it is close to b .

Now when we choose c , why should "b" be the closest number to c ? Why can't we take a pair that satisfies (p,q) p<q<c where p and q are very close. Here i miss the insight.
Since p<a && q<b ,the height formed by them should be smaller is my guess. I think the difference (q-p) and (b-a) also counts in determining the height.

Looks like this is because of sine rule 1/2*a*b*arcsin(b/e) < 1/2*c*d*arcsin(d/e) , sin and arcsin being ans increasing function.






f74956227, my comparision functions are like this, use inline, it may reduce your floating errors i'm not sure though. My eps is 1e-8. double holds precision only for 15 digits or so. So do a sqrt(s* s-a) * sqrt(s* s-b). but using long double you can use the whole thing. But use long double version of sqrt ie sqrtl and i got AC.

Code: Select all

 inline int iseq(double x,double y){
         if (fabs(x-y) < EPS) return true;
         return false;
 }

 inline double area(double x,double y,double z){
         if(x+y < z) return 0.0;
         if(iseq(x+y,z)) return 0.0;
...
}

[f74956227]

Hey! Finally i got AC, the mistake is that we should check each triple in the sorting sequence...
such as: 1 2 3 4 5 (index of decreasing order) => check (1,2,3) (2,3,4) (3,4,5), my original program will break if find a legal area which will be wrong!!

And thank all of your replay for my question

[gaurav2289]

Hi
Will anyone please tell me why i am getting TLE??

I use the following algorithm-
1. Sort all the side lengths in increasing order.
2. Check all three consecutive sides in sorted order and if they form a triangle (i.e. a+b>c), calculate the area using heron's formula.
3. Print the largest area and if no triangle possible then print 0.00.

Following is the implementation of the above algorithm--

Code: Select all

Removed after AC.

[helloneo]

Maybe your sorting algorithm is slow.
And also cin is slow.. you can use scanf() instead.

Ps. Remove your code..

[gaurav2289]

@helloneo
Thanks for your reply. I got AC.
Earlier I was using selection sort algorithm which has complexity O(n^2). Because of that I got TLE.
Now I replaced it with O(nlogn) algorithm (c++ in-built sort algorithm) and got AC.

[Obaida]

my method seems ok to me. But why gets wa? some one plz help me.

Code: Select all

removed

[Igor9669]

Don't break your code! find max area and all will be ok!!!!
And of course delete your code!

[jakir052]

Acc

[helloneo]

This might help

http://acm.uva.es/board/viewtopic.php?t=42630

[zobayer]

double works fine with eps = 1e-9 for me.
also sqrt( s * (s-a) * (s-b) * (s-c) ) works just fine. no need to split them actually.

[yatsen]

I got a lot of WA, what's wrong with my code, anyone help?

Code: Select all

int comp(double *p,double *q)
{
    return *q-*p;   
}

.
.
.

ac , removed