Problem 1027 - Black Ball
Problem 1027 - Black Ball
Time Limit: 1000MS Memory Limit: 65536KB Difficulty:
Total Submit: 17 Accepted: 4 Special Judge: No
Description
Billiards is one of Tiantian's favourite sports. Now, she is playing it with one of her friends, and the game comes to the final ball---Black Eight. The one gets a pot will win the game. Fortunately, it's Tiantian's turn! She wants to win the game more wonderful, so she designs a special route. We assume that the ball will roll forever before being hit into one of the pockets. Let's neglect the middle pocket, and makes two coordinate axes along the edge as shown in the following figure. We know the length (6 shown follows) and width(4 shown follows) of the cushion, and of course the x and y coordinates of the ball. And, finally the angle between the positive direction of the X axes and the starting route is 45°. Will the ball pot?
Input
There are multiple test cases. Each case takes one line and contains 4 integers L, W, x and y(2≤L≤2^31-1, w≤W≤L, 0＜x＜L, 0＜y＜W). They describe the cushion and the position of the ball. The four pockets of the cushion are (0,0), (L,0), (0,W) and (L,W). The initial position of the ball is (x,y). L=0, W=0, x=0, y=0 indicates the end of the input and should not be processed by your program.
Output
For each case, output one line with one single integer. The integer -1 stands for that the ball will never be hit into any pocket. If not, output the corresponding pockets: 0 for (L,W), 1 for (0,W), 2 for (L,0) and 3 for (0,0).
Sample Input
6 4 3 3
4 4 1 3
0 0 0 0
Sample Output
1
-1
Hint
Source
7th Xidian University Collegiate Programming Contest(2009.9)
分析
在一个给定的矩形台球桌上，在给定的位置以45度角击球黑8，问球是否可以进入球桌四个角上的袋，如果可以还要给出进的是哪个袋。
这里隐含了另一个条件，即球桌的摩擦力为零，也就是说球只要不入袋就会在球桌上一直匀速地运动下去，贴库则按反射角反弹。
这样球的运动轨迹是一条折线。这不便于分析。我们将这些折线按其入射方向展开成一条直线，将会发现它们经过的路径正是球桌以各边为对称轴的镜面虚像。
这样，问题就归结到了判断
Lx + L - x0 = Wy + W - y0
这个一次不定方程有没有解，如果有解则其特征解是多少上来了。
重新整理一下，设 C = W - y0 - L + x0，则方程改写为
Lx - Wy = C
方程有解的充要条件是L和W的最大公约数能整除C。
而求取其特征解的过程可以用辗转相除法来做，具体过程不再赘述，有兴起的朋友可以参看数论的相关章节。
如果大家在纸上画一个矩形，并按题目要求标上四个角的编号，然后向四周展开这个矩形的投影以及投影后的编号，就会发现编号与上面方程的一组最小的非负整数解之间存在一种简单的很有意思的对应关系。
所以我想这四个角的编号顺序也是出题者精心设计的。当然即使随便编号也不影响这个题目的运算过程。
程序代码：
#include<stdio.h>
int gcd(int a, int b)
{
int r;
while(r = a % b) a = b, b = r;
return b;
}
long long f(long long a, long long b, long long c)
{
return (abs(b) == 1 ? c : c - a * f(b, a % b, c % b)) / b;
}
int cal(int L, int W, long long x, long long y)
{
int c, g;
c = W - L + x - y;
g = gcd(L, W);
if(c % g) return -1;
L /= g; W /= g; c /= g;
y = f(L, -W, c);
x = (c + W * y) / L;
while(x < 0 || y < 0) x += W, y += L;
return (x & 1) + ((y & 1) << 1);
}
int main()
{
int L, W, x, y;
while(scanf("%d%d%d%d", &L, &W, &x, &y), (L | W | x | y))
printf("%d\n", cal(L, W, x, y));
return 0;
}
