### 10668 - Expanding Rods

Posted:

**Mon Jun 14, 2004 8:15 am**It seems that it's a easy geometry problem. I use Newton-Raphson Method to get the angle of the sector. But I always got WA. Could someone give some input?

Page **1** of **3**

Posted: **Mon Jun 14, 2004 8:15 am**

It seems that it's a easy geometry problem. I use Newton-Raphson Method to get the angle of the sector. But I always got WA. Could someone give some input?

Posted: **Mon Jun 14, 2004 8:33 am**

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

P.S. I got ~25 WAs before AC just because of a silly flaw in my rounding method...

Posted: **Mon Jun 14, 2004 9:03 am**

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)

Posted: **Mon Jun 14, 2004 11:13 am**

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) > 1e-6) and it got WA.

but later I changed to -- while( fabs( low - high) > 1e-10) 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) > 1e-6) and it got WA.

but later I changed to -- while( fabs( low - high) > 1e-10) and it got AC.

Posted: **Mon Jun 14, 2004 12:16 pm**

Can anyone help me with this problem...Im getting WA and I know its precision

[/cpp]

Code: Select all

`Accepted`

Posted: **Mon Jun 14, 2004 12:57 pm**

Two mistakes in your code:

[c]

while(L>0||n>0||C>0)

[/c]

**Suggestion** : Input ends with three negative numbers.

[c]

while(theta>1E-6&&fabs(theta-thetad)>1E-10);

[/c]

change 1e-6 to 1e-10;

Hope it helps.

[c]

while(L>0||n>0||C>0)

[/c]

[c]

while(theta>1E-6&&fabs(theta-thetad)>1E-10);

[/c]

change 1e-6 to 1e-10;

Hope it helps.

Posted: **Mon Jun 14, 2004 2:03 pm**

I changed to 1e-10 but I didnt understand the first comment bout 3 negative numbers.I assume all 3 must be negative to end.

Posted: **Mon Jun 14, 2004 2:19 pm**

Maybe you assume that but your prog doesn'thelmet wrote:I changed to 1e-10 but I didnt understand the first comment bout 3 negative numbers.I assume all 3 must be negative to end.

Ciao!!!

Claudio

Posted: **Mon Jun 14, 2004 3:45 pm**

Nice one CDiMA

To helmet:

0 is not a negative number.

To helmet:

0 is not a negative number.

Posted: **Mon Jun 14, 2004 5:14 pm**

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.

Posted: **Mon Jun 14, 2004 7:18 pm**

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.

Posted: **Mon Jun 14, 2004 9:30 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.

Posted: **Mon Jun 14, 2004 10:56 pm**

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.

Posted: **Tue Jun 15, 2004 6:07 am**

Setting the range of y between 0 and 1.... But I thought that the radius could be very long as well as y. Could you give me more guidelines? I still work on finding the proper range that I could do bisection.

Posted: **Tue Jun 15, 2004 7:07 am**

Thanks to my new found knowledge that 0 is not negative I got it AC...