10668  Expanding Rods
Moderator: Board moderators
10668  Expanding Rods
It seems that it's a easy geometry problem. I use NewtonRaphson Method to get the angle of the sector. But I always got WA. Could someone give some input?
Maybe you could try working on the displacement directly. Dunno if it helps...
Btw, I suspect that there are rods of zero length in the input, so you may think of treating this as a special case.
P.S. I got ~25 WAs before AC just because of a silly flaw in my rounding method...
Btw, I suspect that there are rods of zero length in the input, so you may think of treating this as a special case.
P.S. I got ~25 WAs before AC just because of a silly flaw in my rounding method...
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
I first tried solving the problem by doing a binary search on the radius of the circle, but wasn't able to get this accepted, despite being very careful with accuracy.
Then I did as Observer suggested and performed the search on the actual answer instead, which turned out to work fine.
I guess this is because near C*n=0.5 (the maximum value), the answer has a very sensitive dependence on the radius.
(And yeah, there are rods in the input with C*n > 0.5 and l = 0)
Then I did as Observer suggested and performed the search on the actual answer instead, which turned out to work fine.
I guess this is because near C*n=0.5 (the maximum value), the answer has a very sensitive dependence on the radius.
(And yeah, there are rods in the input with C*n > 0.5 and l = 0)
my suggestion
These are the two equations that I got...
L' = r * ang;
L = 2 * r * sin(ang/2);
where r = radius and ang = angle at the center..
Later I applied B.search on L'/L  ang/(2*sin(ang/2) )= 0 to find the value
of ang...
And finally answer = r  r*cos(ang/2);
I initially apllied  while( fabs( low  high) > 1e6) and it got WA.
but later I changed to  while( fabs( low  high) > 1e10) and it got AC.
L' = r * ang;
L = 2 * r * sin(ang/2);
where r = radius and ang = angle at the center..
Later I applied B.search on L'/L  ang/(2*sin(ang/2) )= 0 to find the value
of ang...
And finally answer = r  r*cos(ang/2);
I initially apllied  while( fabs( low  high) > 1e6) and it got WA.
but later I changed to  while( fabs( low  high) > 1e10) and it got AC.
WA...surely some precision error
Can anyone help me with this problem...Im getting WA and I know its precision
[/cpp]
Code: Select all
Accepted
Last edited by helmet on Tue Jun 15, 2004 7:06 am, edited 1 time in total.
Just another brick in the wall...
minor mistake
Two mistakes in your code:
[c]
while(L>0n>0C>0)
[/c]
Suggestion : Input ends with three negative numbers.
[c]
while(theta>1E6&&fabs(thetathetad)>1E10);
[/c]
change 1e6 to 1e10;
Hope it helps.
[c]
while(L>0n>0C>0)
[/c]
Suggestion : Input ends with three negative numbers.
[c]
while(theta>1E6&&fabs(thetathetad)>1E10);
[/c]
change 1e6 to 1e10;
Hope it helps.
Re: WA still
Maybe you assume that but your prog doesn'thelmet wrote:I changed to 1e10 but I didnt understand the first comment bout 3 negative numbers.I assume all 3 must be negative to end.
Ciao!!!
Claudio
I used almost the same method as sohel, but using nr method. This code got TLE. This is my first code using nr method to solve the equation. Could someone give some advice on my code? Or using bisection could be better? I'm poor at computer numerical method and hoping someone to help me solve problems like this.
My experience (learned through much frustration ) is that NR is almost useless in contest problems like this, mainly because of stability issues. It's much easier to get a bisection routine working and stable, and for simple equation solving like this, you won't notice any speed difference.htl wrote:I used almost the same method as sohel, but using nr method. This code got TLE. This is my first code using nr method to solve the equation. Could someone give some advice on my code? Or using bisection could be better? I'm poor at computer numerical method and hoping someone to help me solve problems like this.
So yeah, my advice would be to switch to bisection.

 New poster
 Posts: 20
 Joined: Thu Apr 10, 2003 10:53 pm
Per, I had the same problem during the contest. I did binary search on the radius, which is not precise enough. I guess if you have a really small difference like 0.0000001, the radius can be huge, and with the formula I used, that meant taking the cos of something very close to 0. Searching on the angle would have similar problems. But I got tunnel vision and didn't realize this. I prefer to think about algorithms, and not implementation details like FP precision.
I do know someone who got the binary search on the radius to work, by using long doubles and implementing his own cos function. Wish I'd thought of that.
I do know someone who got the binary search on the radius to work, by using long doubles and implementing his own cos function. Wish I'd thought of that.
In the contest I wrote binary search on radius (or, more exactly, on the y coordinate of the center) using doubles and got it AC on the first attempt
Algorithm:
Handle cases where L' is near L and when it is near PI * L / 2.
Set y=1. While the arc is too long, double y. Then bsearch with initial bounds 0 and y.
When you have a fixed y, you compute the radius r=sqrt( sqr(y) + sqr(L/2) ). Note that r=y+x, where x is the answer. To compute the length of the arc, compute the angle using atan2.
My opinion is that precision errors may arise in boundary cases (especially in the case when y is almost zero). If you don't handle them separately, check whether your solution gives the correct answer in these cases.
Algorithm:
Handle cases where L' is near L and when it is near PI * L / 2.
Set y=1. While the arc is too long, double y. Then bsearch with initial bounds 0 and y.
When you have a fixed y, you compute the radius r=sqrt( sqr(y) + sqr(L/2) ). Note that r=y+x, where x is the answer. To compute the length of the arc, compute the angle using atan2.
My opinion is that precision errors may arise in boundary cases (especially in the case when y is almost zero). If you don't handle them separately, check whether your solution gives the correct answer in these cases.