## 11579 - Triangle Trouble

Moderator: Board moderators

f74956227
New poster
Posts: 37
Joined: Sun Jan 27, 2008 1:50 am
Location: Taiwan
Contact:

### 11579 - Triangle Trouble

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
``````
Last edited by f74956227 on Sat Feb 28, 2009 1:47 am, edited 1 time in total.
electron

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:

### Re: 11579 - Triangle Trouble

The identifier for long double is '%Lf'.
Ami ekhono shopno dekhi...
HomePage

f74956227
New poster
Posts: 37
Joined: Sun Jan 27, 2008 1:50 am
Location: Taiwan
Contact:

### Re: 11579 - Triangle Trouble

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

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:

### Re: 11579 - Triangle Trouble

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.
Ami ekhono shopno dekhi...
HomePage

tryit1
Experienced poster
Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

### Re: 11579 - Triangle Trouble

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;
...
}
``````
Last edited by tryit1 on Sat Feb 28, 2009 1:52 am, edited 2 times in total.

f74956227
New poster
Posts: 37
Joined: Sun Jan 27, 2008 1:50 am
Location: Taiwan
Contact:

### Re: 11579 - Triangle Trouble

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
electron

gaurav2289
New poster
Posts: 10
Joined: Tue Jul 07, 2009 11:59 am
Location: Ithaca, NY

### Re: 11579 - Triangle Trouble

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.``
Last edited by gaurav2289 on Tue Jul 07, 2009 5:41 pm, edited 1 time in total.

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

### Re: 11579 - Triangle Trouble

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

gaurav2289
New poster
Posts: 10
Joined: Tue Jul 07, 2009 11:59 am
Location: Ithaca, NY

### Re: 11579 - Triangle Trouble

@helloneo
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
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am

### Re: 11579 - Triangle Trouble

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

Code: Select all

``removed``
Last edited by Obaida on Wed Jul 22, 2009 5:05 pm, edited 1 time in total.
try_try_try_try_&&&_try@try.com
This may be the address of success.

Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

### Re: 11579 - Triangle Trouble

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

jakir052
New poster
Posts: 3
Joined: Sat Jun 26, 2010 11:27 am

### 11579 - Triangle Trouble

Acc
Last edited by jakir052 on Thu Apr 28, 2011 7:05 pm, edited 1 time in total.

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

### Re: 11579 - Triangle Trouble

zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Contact:

### Re: 11579 - Triangle Trouble

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.
You should not always say what you know, but you should always know what you say.

yatsen
Learning poster
Posts: 68
Joined: Fri Nov 23, 2001 2:00 am
Location: taiwan

### Re: 11579 - Triangle Trouble

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
``````
Last edited by yatsen on Mon Nov 21, 2011 7:45 am, edited 1 time in total.