10834 - The Story of Two Coins

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

Moderator: Board moderators

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

10834 - The Story of Two Coins

Post by Cho » Thu Mar 24, 2005 9:19 am

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
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

hmm

Post by shahriar_manzoor » Thu Mar 24, 2005 10:39 am

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

Think about other possible mistakes :D

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

Post by Cho » Thu Mar 24, 2005 11:08 am

Thx.
It turns out that I don't know the returned value from atan2 is in the range (-pi,pi]. :oops:

shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

hmm

Post by shahriar_manzoor » Thu Mar 24, 2005 11:36 am

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

Post by misof » Thu Mar 24, 2005 1:18 pm

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
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

Re: hmm

Post by shahriar_manzoor » Thu Mar 24, 2005 1:44 pm

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:

Post by mf » Thu Mar 24, 2005 2:10 pm

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.

See this page: http://www.opengroup.org/onlinepubs/009 ... atan2.html

shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

hmm

Post by shahriar_manzoor » Thu Mar 24, 2005 3:00 pm

Yes I replied like a stupid. :oops:

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

Re: hmm

Post by Cho » Thu Mar 24, 2005 3:45 pm

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

Post by david » Thu Mar 24, 2005 4:19 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;
}

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Sun Apr 10, 2005 10:00 pm

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

Post by david » Mon Apr 11, 2005 10:19 pm

Thanks for replying.
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

Post by Antonio Ocampo » Tue Apr 12, 2005 12:24 am

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 8)

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Tue Apr 12, 2005 12:31 am

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

Post by david » Fri Apr 15, 2005 3:39 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.

Post Reply

Return to “Volume 108 (10800-10899)”