## 10668 - Expanding Rods

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

Moderator: Board moderators

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

### 10668 - Expanding Rods

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?

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
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...
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
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)

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

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

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

helmet
New poster
Posts: 31
Joined: Tue Mar 02, 2004 11:55 am

### WA...surely some precision error

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

Code: Select all

``Accepted``
[/cpp]
Last edited by helmet on Tue Jun 15, 2004 7:06 am, edited 1 time in total.
Just another brick in the wall...

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### minor mistake

Two mistakes in your code:

[c]
while(L>0||n>0||C>0)

[/c]

Suggestion : Input ends with three negative numbers.

[c]

[/c]

change 1e-6 to 1e-10;

Hope it helps.

helmet
New poster
Posts: 31
Joined: Tue Mar 02, 2004 11:55 am

### WA still

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.
Just another brick in the wall...

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

### Re: WA still

helmet 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.
Maybe you assume that but your prog doesn't
Ciao!!!

Claudio

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
Nice one CDiMA

To helmet:
0 is not a negative number.

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan
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.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
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.
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.

So yeah, my advice would be to switch to bisection.

Lars Hellsten
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.

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 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.

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan
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.

helmet
New poster
Posts: 31
Joined: Tue Mar 02, 2004 11:55 am

### yahoo

Thanks to my new found knowledge that 0 is not negative I got it AC...
Just another brick in the wall...