11579 - Triangle Trouble

All about problems in Volume 115. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

11579 - Triangle Trouble

Post by f74956227 » Fri Feb 27, 2009 11:28 am

Could someone help me with the problem? i got WA many times... :evil:
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
Location: Dhaka, Bangladesh
Contact:

Re: 11579 - Triangle Trouble

Post by Jan » Fri Feb 27, 2009 12:16 pm

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

Post by f74956227 » Fri Feb 27, 2009 2:32 pm

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

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

Re: 11579 - Triangle Trouble

Post by Jan » Fri Feb 27, 2009 2:42 pm

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

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

Re: 11579 - Triangle Trouble

Post by tryit1 » Sat Feb 28, 2009 12:49 am

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

Post by f74956227 » Sat Feb 28, 2009 1:45 am

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 :D
electron

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

Re: 11579 - Triangle Trouble

Post by gaurav2289 » Tue Jul 07, 2009 3:46 pm

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

Post by helloneo » Tue Jul 07, 2009 4:23 pm

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

Ps. Remove your code.. :-)

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

Re: 11579 - Triangle Trouble

Post by gaurav2289 » Tue Jul 07, 2009 5:40 pm

@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
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 11579 - Triangle Trouble

Post by Obaida » Tue Jul 21, 2009 2:32 am

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

Post by Igor9669 » Wed Jul 22, 2009 8:30 am

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

Post by jakir052 » Fri Aug 20, 2010 12:32 pm

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

Post by helloneo » Sat Aug 21, 2010 4:48 pm


zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Location: CSE-DU, Bangladesh
Contact:

Re: 11579 - Triangle Trouble

Post by zobayer » Mon Jan 24, 2011 8:44 am

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

Post by yatsen » Mon Nov 21, 2011 5:09 am

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.

Post Reply

Return to “Volume 115 (11500-11599)”