10668 - Expanding Rods

[htl]

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]

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

[Per]

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]

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]

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

Code: Select all

Accepted

[/cpp]

[sohel]

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.

[helmet]

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.

[CDiMa]

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]

Nice one CDiMA

To helmet:
0 is not a negative number.

[htl]

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]

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]

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]

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]

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]

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