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

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

Post by Antonio Ocampo » Mon Apr 18, 2005 3:32 am

Hi david, you have to delete your code in your previous post.

About

Code: Select all

I changed the code to avoid printing -0.000, switched back to doubles (instead of long doubles) and got AC. 
These are frequent troubles in our source codes.

Keep posting

Victor Barinov
New poster
Posts: 24
Joined: Sun Oct 03, 2004 10:03 am

10834 - The Story of Two Coins. Help, please!

Post by Victor Barinov » Sat Apr 30, 2005 7:47 pm

Hello everybody!
I can not understand what is wrong with my code. I always get WA. Maby anyone give me some tests or hints?.

Thanks!

Here is my code:

Code: Select all

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

#define  Pi 3.1415926535897932384626433832795
#define  eps 1e-8

int  main()
{
  int  cas = 0;
  double  R, r, tx, ty, px, py;
  double  alpha, gamma, phi1, phi2;
  
  while  (1)
  {
    scanf("%lf%lf%lf%lf", &R, &r, &tx, &ty);
    if  (r == 0.0 && R == 0.0)  break;
    
    cas++;
    printf("Case %d:\n", cas);
    
    if  (tx*tx + ty*ty - R*R <= eps  ||  tx*tx + ty*ty - (R+2.0*r)*(R+2.0*r) >= -eps) {
      printf("IMPOSSIBLE\n"); continue; }
    
    alpha = acos(tx / sqrt(tx*tx + ty*ty));
    if  (ty < 0)  alpha = 2.0*Pi - alpha;
    
    gamma = acos( (R*R + tx*tx + ty*ty + 2.0*R*r) / (2.0*(R+r)*sqrt(tx*tx + ty*ty)) );
    
    phi1 = alpha - gamma;  if  (phi1 < 0.0)  phi1 += 2.0*Pi;
    phi2 = alpha + gamma;
    
    if  (phi1 > phi2) {
      alpha = phi1;
      phi1 = phi2;
      phi2 = alpha;
    }
    
    px = (R+r-r*sin(phi1*R/r))*cos(phi1) - r*cos(phi1*R/r)*sin(phi1);
    py = (R+r-r*sin(phi1*R/r))*sin(phi1) + r*cos(phi1*R/r)*cos(phi1);
    if  (px < 0.0  &&  px > -0.0005)  px = 0.0;
    if  (py < 0.0  &&  py > -0.0005)  py = 0.0;
    printf("%.3lf %.3lf\n", px, py);
    
    px = (R+r-r*sin(phi2*R/r))*cos(phi2) - r*cos(phi2*R/r)*sin(phi2);
    py = (R+r-r*sin(phi2*R/r))*sin(phi2) + r*cos(phi2*R/r)*cos(phi2);
    if  (px < 0.0  &&  px > -0.0005)  px = 0.0;
    if  (py < 0.0  &&  py > -0.0005)  py = 0.0;
    printf("%.3lf %.3lf\n", px, py);
  }
  
  return 0;
}


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

hmm

Post by shahriar_manzoor » Sun May 01, 2005 4:27 am

I am at a PC now which does not have a C/C++ compiler so I could not check. But does your program consider the following line

"The coordinates of P should be printed in chronological order (If a position is reached by the second coin before the other position then the corresponding coordinates of P should be printed first)."

filipius
New poster
Posts: 2
Joined: Thu Sep 28, 2006 11:07 am

Post by filipius » Fri Nov 03, 2006 1:42 pm

Hi,

You made this question a long time ago, but I used your code to understand what was wrong with mine. Finally, I got accepted and in the process I found your bug (well, at least one bug - and, of course you may have found it already, but this can help someone else):

In same cases, your angle phi2 is larger than 2 * pi.
This makes a difference in the position of P, because the coins have different sizes.
For instance, consider the following input:

830 714 1892.70526225 -288.736962726

your program's wrong output:
1404.649 -39.541
801.511 390.331

correct output:

1204.633 959.680
1404.649 -39.541

You must normalize your angles.

Cheers,

Filipe Araujo.
Univ. of Coimbra
Portugal

Post Reply

Return to “Volume 108 (10800-10899)”