1997 ACM South Central USA Problem 5: Shoes

1997 ACM South Central USA Programming Contest

Problem #5: Horse Shoe Scoring Source File: shoes.{pas,cpp,c,ss} Input File: shoes.dat Output File: shoes.out Comments

The game of horseshoes is played by tossing horseshoes at a post that is driven into the ground. Four tosses generally make up a game. The scoring of a toss depends on where the horseshoe lands with respect to the post. If the center of the post is within the region bounded by the interior of the horseshoe and the imaginary line connecting the two legs of the horseshoe, and the post is not touching the horseshoe, it is a "ringer" and worth five points. If any part of the horseshoe is touching the post, it is a "toucher" and worth 2 points. If the toss is neither a ringer nor a toucher and some part of the horseshoe will touch the post when it is pivoted around its point B, it is a "swinger" and worth 1 point. Any horseshoe which does not fit any of the scoring definitions scores zero points. See the figures below for examples of each of the scoring possibilities.

This program uses mathematical horseshoes that are semicircles with radius 10 centimeters. The location of the horseshoe is the given by two points: the centerpoint of the semicircle, measured in centimeters relative to x and y axes, and the point that exactly bisects the semicircle. The post is at location (0,0) and is 2 centimeters in diameter. The top of the post is level with the ground allowing the horseshoe to lay on top of the post; therefore, a "toucher" would mean that any part of the horseshoe lies within the circle with a radius of 1 centimeter centered at (0, 0).

Each "turn" consists of four tosses. The purpose of your program is to determine the score of the "turn" by computing the sum of the point values for each of the four tosses.

Input

Input to your program is a series of turns, and a turn consists of four horseshoe positions. Each line of input consists of two coordinate pairs representing the position of a toss. Each coordinate consists of a floating point (X,Y) coordinate pair (-100.0 <= X, Y <= 100.0) with up to 3 digits of precision following the decimal point; the first and second numbers are the X and Y coordinates of the centerpoint of the horseshoe semicircle (Point A) and the third and fourth numbers are the X and Y coordinates of the point (B) which bisects the horseshoe semicircle. You can be assured that the distance between points A and B for each horseshoe will be exactly 10 centimeters. The figure below illustrates the meanings of the values on each line.

The first four lines of input define the horseshoe positions for the first turn; lines 5 through 8 define the second turn, etc. There are at most 999 turns in the input file, and every turn contains four horseshoe positions. Your program should continue reading input to the end of file.

Output

The first line of output for your program should be the string "Turn Score" in columns 1 through 10. For each "turn", your program should print the number of the turn right-justified in columns 1-3 (turns are numbered starting with 1), a single space (ASCII character 32 decimal) in columns 4 and 5, and the score for the turn right-justified in columns 6 and 7 with a single leading blank for scores 0 to 9. Numbers that are right-justified should be preceded by blanks, not zeroes, as the fill character.

Sample Input

76.5 53.3 76.5 43.3
-5.1 1.0 4.9 1.0
5.1 0.7 5.1 -9.3
7.3 14.61 7.3 4.61
23.1 17.311 23.1 27.311
-23.1 17.311 -23.1 27.311
-23.1 -17.311 -23.11 -27.311
23.1 -17.311 23.1 -27.311
0.0 7.0 -6.0 -1.0
18.0 -24.0 9.0 -12.0
4.0 9.0 4.0 -1.0
-10.0 -13.0 -19.0 -25.0

Sample Output

Turn Score
1    10
2     0
3     7

Judge's Input

Judge's Output

Turn Score
1    10
2     0
3     7
4    10

Solution

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

#define sqr(x) ((x)*(x))
#define POLE_RAD 1.
#define SHOE_RAD 10.
#define SHOE_CHORD (5*sqrt(2.))
#define NUM_TOSSES 4

#define RINGER 5
#define TOUCHER 2
#define SWINGER 1

int main(void)
{
FILE *inf = fopen("shoes.dat","r");
FILE *outf= fopen("shoes.out","w");

int turn;
fprintf(outf, "Turn Score\n");
for (turn = 1; !feof(inf); turn++)
    {
      int score = 0, shoe_count;
      for (shoe_count = 0; shoe_count < NUM_TOSSES; shoe_count++)
        {
          float ax, ay, bx, by;
          float px, py;
          fscanf(inf, "%f %f %f %f\n", &ax, &ay, &bx, &by);

          /* translate and rotate to put A at origin, B on y axis and pole at
             (px,py) */
          bx -= ax;
          by -= ay;
          px = -(by * ax - bx * ay) / SHOE_RAD;
          py = -(bx * ax + by * ay) / SHOE_RAD;

          if (px < 0.) px = -px;
          if (py >= 0)
            {
              float dist_a = sqr(px)+sqr(py);
              if (dist_a < sqr(SHOE_RAD-POLE_RAD))
                score += RINGER;
              else if (dist_a < sqr(SHOE_RAD+POLE_RAD))
                score += TOUCHER;
              else
                {
                  float dist_b = sqr(px) + sqr(py-SHOE_RAD);
                  if (dist_b <= sqr(SHOE_CHORD+POLE_RAD))
                    score += SWINGER;
                }
            }
          else
            {
              float dist_leg = sqr(px-SHOE_RAD) + sqr(py);
              if (dist_leg < POLE_RAD)
                score += TOUCHER;
              else
                {
                  float dist_b = sqr(px) + sqr(py-SHOE_RAD);
                  if (dist_b <= sqr(SHOE_CHORD+POLE_RAD))
                    score += SWINGER;
                }
            }
        }
      fprintf(outf, "%3d %2d\n", turn, score);
    }
fclose(inf);
fclose(outf);
return 0;
}

Comments

There were many problems with this problem that may have resulted in it being misjudged. The description as distributed gave the shoe diameter as 10cm, where the sample input provided shoes with radius 10cm. The sample output, as presented then, was not correct. We apologize for these difficulties and will seek to avoid them next year.