## 10668 - Expanding Rods

Moderator: Board moderators

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
Please give some test cases that can cause precision errors and is the angle at the center at most 45'??
"Everything should be made simple, but not always simpler"

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
The angle at the center can be more than 45...

... infact I assumed the highest value to be pi - 1e-10;

One critical thing that comes to mind is if either C or N is equal to 0 then the output is zero straight away.

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm
htl wrote: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.
Of course, the radius can be very long and we don't know an upper limit, therefore (I repeat myself) we do the following:
misof wrote:Set y=1. While the arc is too long, double y. Then bsearch with initial bounds 0 and y.
You probably overlooked/didn't understand the part "double y", meaning you should multiply y by 2 until the corresponding arc is short enough. In this way you find some upper bound (in logarithmic time) and then you can start searching in the range (0,y).

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
I got ac now. just expanding the limit of pi and checking c==0 and n==0.
"Everything should be made simple, but not always simpler"

udvat
New poster
Posts: 29
Joined: Thu Aug 07, 2003 9:56 pm

### 10668

wud anyone plz check my code?

code has been removed
Last edited by udvat on Mon Jun 28, 2004 6:54 pm, edited 1 time in total.

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
I gave the following input to your program and it hanged.
• 15 415 0.0044

udvat
New poster
Posts: 29
Joined: Thu Aug 07, 2003 9:56 pm

### thankx

thank u very much shamim. I got accepted.

Gigi's Baby
New poster
Posts: 19
Joined: Thu May 02, 2002 5:47 am
Location: Zhongshan (Sun Yat-sen) University
I think it is easier to bsearch the answer.

so r^2-(r-x)^2=(l/2)^2 => r=(l^2/x/4+x)/2;

angle= 2arcsin(l/2/r)
l'' = r*angle

compare l'' with l' to run the bsearch

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
Could someone post some critical test cases pls ?

I tried almost everything, I mean binary search on the
different end conditions - still WA.

I even rewrote my C++ program in Java and still WA.
The C++ program uses long double and the Java
program uses double as there is no long double
in Java.

The interesting fact is that my program only runs for 0.000
or 0.002 secs before getting WA. So it should be some
obvious problem which still I do not discover for the moment.

Any ideas are welcome Thanks in advance.

P.S.
I hate posting code so I am not doing it for the moment.
Although I am sure it is some very very small bug.

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
I got ACC, do not bother to answer me.

I just want to make a remark that could be of some
use in my opinion. My problem was the following one.

I was calling the function abs() with a long double argument.
My environment is VS .NET so I have as a built-in function
long double abs(long double)
Unfortunately when such code gets executed on the Judge's
Machine it actually produces a call to
int abs(int). In one of the emails from the Judge I suddenly
got a strange warning saying:
"03830241_24.c:34: warning: `long double' used
for argument 1 of `abs(int)' "

which made me suspect what I described above.

After writing on my own one new function
long double absLD(long double)
and after calling that function instead of
long double abs(long double)
I managed to get ACC immediately.

That was the reason I was getting all the time WA.
My code has just been behaving in a completely
different way on Judge's machine than on my machine.

Good luck to everyone !

ibroker
New poster
Posts: 18
Joined: Tue Nov 08, 2005 6:38 pm

### 10668 why wronged

I got two equation.

L' = (1+nC)L = 2rθ ---- (1)
L = 2rsinθ ---- (2)

2rθ/(1+nC) = 2rsinθ
-> θ = sinθ(1+nC)

I dirrerenciate this equation.
so 1 = cosθ(1+nC)
-> θ = acos(1/(1+nC))

so I could know radious 'r' using equation (2) or (1)
so I could got a correct answer
BUT!!! may be this method is a wrong.
I can't have correct answer in example data case.

PLZ teach me why this method incorrect.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

### Re: 10668 why wronged

Hi,

Of course this method doesn't work!

Consider θ = 2sinθ
Using your method, we get 1 = 2cosθ
=> θ = pi/3
but then 2sinθ = sqrt(3), i.e. your method fails...

And the reason why it fails is obvious. For a given t,
1. f(t) = g(t) does NOT imply that f'(t) = g'(t).
2. f'(t) = g'(t) does NOT imply that f(t) = g(t).
These can be seen easily from a graph.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

ibroker
New poster
Posts: 18
Joined: Tue Nov 08, 2005 6:38 pm

### Re: 10668 why wronged

//Observer thanks
I got ACC but I have one more question.
I use bsearch to find out of theta.
But I got WA. because I use 'long double'
I don't know why 'long double' was wrong, and 'double' was correct.
I only change 'long double' of 'double'. and I got ACC.
Why?

ayeshapakhi
Learning poster
Posts: 60
Joined: Sun Apr 16, 2006 7:59 pm
i'm getting wa..
i used bisection for the centered angle made by the chord...
someone pls tell what i'm missing...

Code: Select all

``````#include <stdio.h>
#include <math.h>

#define err 1e-10
//deleted after acc.
``````
thanks.
Last edited by ayeshapakhi on Fri Apr 06, 2007 4:45 pm, edited 1 time in total.

ayeshapakhi
Learning poster
Posts: 60
Joined: Sun Apr 16, 2006 7:59 pm

### 10668 wa

Pls someone provide me some testcases.
it seems tough to avoid precision errors...

i would be highly thankful..