10834 - The Story of Two Coins

Moderator: Board moderators

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

10834 - The Story of Two Coins

It's possible that, given (x,y), there is only one possible position for the moving second coin to touch (x,y). How should this case be handled? e.g:

Code: Select all

``````5 5 5 0
0 0 0 0``````
Should the output be:

Code: Select all

``````Case 1:
10.000 5.000
10.000 5.000``````
or:

Code: Select all

``````Case 1:
10.000 5.000``````
Or simply assume there is no such case?

shahriar_manzoor
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

hmm

There is no such input that only one solution is posible.

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong
Thx.
It turns out that I don't know the returned value from atan2 is in the range (-pi,pi].

shahriar_manzoor
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

hmm

To determine an angle in the range (0,360) degree only one trigonometric ratio is not enough. Use sin(theta) and cos(theta) together to uniquely determine an angle. As sinthete is positive in quadrant 1 and 2 and costheta is positive in quadrant 4 and 1. So their sign will indicate where the angle actually is (Qudrant 1, 2, 3, or 4). Hope it helps.

Or may be I talk too much and you have already solved this problem.

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Re: hmm

shahriar_manzoor wrote:To determine an angle in the range (0,360) degree only one trigonometric ratio is not enough. Use sin(theta) and cos(theta) together to uniquely determine an angle. As sinthete is positive in quadrant 1 and 2 and costheta is positive in quadrant 4 and 1. So their sign will indicate where the angle actually is (Qudrant 1, 2, 3, or 4). Hope it helps.

Or may be I talk too much and you have already solved this problem.
One ratio may not be enough... but atan2() surely is. (The function is in math.h, in cmath and I believe that even FreePascal has a similar function.)

atan2(y,x) returns the oriented angle from the vector [1,0] to the vector [x,y].
The only mistake Cho made is that he probably assumed this angle to be from the range [0,2pi), whereas the function returns an angle from (-pi,pi].

Shahriar: using atan2() is much easier and less error-prone than handling the 4 cases you mention "by hand".

shahriar_manzoor
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

Re: hmm

misof wrote:
shahriar_manzoor wrote:atan2(y,x) returns the oriented angle from the vector [1,0] to the vector [x,y].
The only mistake Cho made is that he probably assumed this angle to be from the range [0,2pi), whereas the function returns an angle from (-pi,pi].

Shahriar: using atan2() is much easier and less error-prone than handling the 4 cases you mention "by hand".
yes! I never used atan2(), and never knew its utility, now I understand why this function exists.

But atan2(y,x), fails when x is zero. So one should handle this case manually? isn't it? That's why I still find the use of sin and cos more robust although atan2() seems fine otherwise

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
No, atan2() fails only when both y and x are zero (in this case the return value is implementation-specific). When only x is zero, the function must return either pi/2 or -pi/2, depending on the sign of y.

shahriar_manzoor
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

hmm

Yes I replied like a stupid.

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Re: hmm

shahriar_manzoor wrote:I never used atan2(), and never knew its utility, now I understand why this function exists.
This is the same as my case. I don't know the existence of such a handy function until very recently somebody mentioned this function in the forum for solving other problem.

david
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm
Can anyone tell me why this code returns WA? (The code is a bit ugly but very simple, just computes the angle 'a' the center of the coin has rotated, and then the position of T).
I have used long doubles to account for precision errors.

By the way, are there any test cases in which the coin has not moved? (this could give wrong answer if the angle, which should be zero, is computed as a small negative number, and thus the program draws the conclusion that the coin has almost completed a turn, but I have handled this with an epsilon of 1e-9).

Code: Select all

``````/* 10834 */
#include <stdio.h>
#include <math.h>

#define error (1e-9)

int main() {
int caso, iR, ir;
long double R, r, x, y, cosd, sind, d, cosg, sing, cosa, sina, a, b, aant, x0, y0, x1, y1;

for (caso = 1;; caso++) {
scanf("%i %i %llf %llf", &iR, &ir, &x, &y);
if (iR == 0 && ir == 0) break;

R = iR;
r = ir;

d = sqrtl(x * x + y * y);

printf("Case %u:\n", caso);
if (R >= d - error || d >= R + 2 * r - error) { puts("IMPOSSIBLE"); continue; }

cosd = ((R + r) * (R + r) + d * d - r * r) / (2 * d * (R + r));
sind = sqrtl(1 - cosd * cosd);

cosg = x / d;
sing = y / d;

/* g+d , el otro es g-d*/
cosa = cosg * cosd - sing * sind;
sina = sing * cosd + cosg * sind;

a = atan2l(sina, cosa);
if (a <= -error) a += 4 * acosl(0);
b = a * R / r;
x0 = (R + r) * cosa - r * sinl(b + a);
y0 = (R + r) * sina + r * cosl(b + a);

aant = a;
cosa = cosg * cosd + sing * sind;
sina = sing * cosd - cosg * sind;

a = atan2l(sina, cosa);
if (a <= -error) a += 4 * acosl(0);
b = a * R / r;
x1 = (R + r) * cosa - r * sinl(b + a);
y1 = (R + r) * sina + r * cosl(b + a);

if (aant <= a)
printf("%.3llf %.3llf\n%.3llf %.3llf\n", x0, y0, x1, y1);
else
printf("%.3llf %.3llf\n%.3llf %.3llf\n", x1, y1, x0, y0);

}

return 0;
}
``````

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
The proper way to read and print long doubles is with %Lf, not with %llf.

Make sure to print 0.000 instead of -0.000.

david
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm
Krzysztof Duleba wrote:The proper way to read and print long doubles is with %Lf, not with %llf.
I haven't had any problems so far using %llf (just as %lli for long longs).
In any case changing this leads to WA again.
Krzysztof Duleba wrote:Make sure to print 0.000 instead of -0.000.
But when should I do so? If a number is -0.0002, the logical thing to print is -0.000, because it is negative. Are you suggesting that any number strictly between -0.001 and 0.001 should be shown as 0.000? If so, this seems to me a rather queer requirement.

Could someone test my program against the output of an accepted program to see if there are any differences?

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per
Hi david. I think that "double" is enough for this problem. In addition, you have to use "sqrt","cos" y "sin" instead of "sqrtl","cosl" and sinl".

Hope it helps

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
david wrote:I haven't had any problems so far using %llf (just as %lli for long longs).
Well, the manual says nothing about %llf and using %llf on my system results in reading junk and printing zeros. But if it works for you and for OJ than I guess it's fine.
david wrote:But when should I do so? If a number is -0.0002, the logical thing to print is -0.000, because it is negative.
I agree with you, but my code failed until I added a line that looks like (using your variable names)

Code: Select all

``if(x0 < 0 && x0 > -error)x0 = 0;``
The same x1, y0, y1.

david
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm
Thanks for that. I changed the code to avoid printing -0.000, switched back to doubles (instead of long doubles) and got AC.
But I don't know how on earth one could have guessed that was the problem. I think the judge shouldn't test for an exact match in floating point problems.