TopCoder problem "NCushion" used in TCO '03 Semifinals 1 (Division I Level Three)



Problem Statement

    Note to plugin users: There are images in this problem statement, please use the applet to view them

Three cushion billiards is a form of Carombole, a French game of billiards. The game is played on a standard billiard table with no pockets, and with three balls: two white cue balls and one red ball. Each player must hit his/her own cue ball such that it hits at least three cushions (or sides), the opponent's cue ball, and the red ball. The cue ball can hit the cushions and the other two balls in any order, but it must hit the cushions before the last ball is hit. These cushions need not be different. For example, you could hit one cushion, then the opposite, then hit the first cushion again, and this counts as 3 cushions.

We're going to invent a new game called N-Cushion billiards, where you only have to hit your opponent's cue ball (there is no red ball), but the number of cushions you must hit before hitting the opponent's ball can be up to 500. In the original game, you could hit more than three cushions, but in this game, you must hit the specified number of cushions exactly.

When a ball bounces off a cushion, the path the ball takes is very similar to light reflecting off a mirror. The image below shows a ball (in red) "reflecting" off a cushion. Notice how the angle of incidence (designated by the ? symbol) is the same on both sides of the reflection.

When a ball goes exactly into a corner, the ball hits both cushions simultaneously (this counts as hitting two cushions), and reflects back exactly in the opposite direction.

Our coordinate system is going to be in millimeters, and points will be written as (X,Y). The table is 2 meters by 1 meter, with the long side lying on the X-axis. The lower left corner is given the coordinate (0,0) and the upper right corner is given the coordinate (2000,1000). You will be given two coordinates in a int[] cue representing your ball, and a int[] opponent representing your opponent's ball. Each int[] will contain exactly 2 elements, the first being the X position, and the second being the Y position. Finally, you will be given an int N, which is the number of cushions your ball must hit before htting the opponent's ball. Your method must return the number of different directions in which you can hit your ball so that it hits the given number of cushions and finally hits the opponent's ball. For the purposes of this problem, assume the balls have no physical size, but are just points in space -- this means your ball must hit the other ball dead on in order to hit it. Remember that your ball cannot pass through the other ball in order to hit the correct number of cushions (see Example 1).

 

Definition

    
Class:NCushion
Method:numShots
Parameters:int[], int[], int
Returns:int
Method signature:int numShots(int[] cue, int[] opponent, int N)
(be sure your method is public)
    
 

Notes

-Assume there is no spin possible, and you cannot jump the ball.
-Assume there is no friction, so your ball does not slow down, and can always hit the required number of cushions.
 

Constraints

-cue will contain exactly two elements.
-opponent will contain exactly two elements.
-cue[0] and opponent[0] will be between 1 and 1999, inclusive.
-cue[1] and opponent[1] will be between 1 and 999, inclusive.
-cue and opponent will not contain the exact same coordinates.
-N will be between 0 and 500, inclusive.
 

Examples

0)
    
{100,100}
{1900,900}
1
Returns: 4
It is possible to hit the opponent's ball by bouncing yours off any of the four cushions first.
1)
    
{100,100}
{1900,100}
1
Returns: 3
It is possible to bounce your ball off the left, bottom, or top cushions, but in order to bounce it off of the right cushion, you would have to hit the ball through the opponent's ball.
2)
    
{500,500}
{1500,500}
2
Returns: 6
The 6 different shots are shown below. The black filled circle is your ball's starting position, the white filled circle is the opponent's ball, and each colored line is a shot which bounces off of two cushions before hitting the other ball.

3)
    
{1222,440}
{276,566}
445
Returns: 1779
A reasonably large example.
4)
    
{20,25}
{40,50}
2
Returns: 8
Don't forget the case where you hit the ball directly into the corner, that counts as hitting two cushions.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=1963

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4706&pm=1963

Writer:

schveiguy

Testers:

lbackstrom , vorthys

Problem categories:

Brute Force, Geometry