这道题先写了暴力模拟 感觉特别麻烦 而且写得很乱 错了三次
就是当还没有射到角落里的时候 就不断反射
int mirrorReflection(int p, int q) {
int wall = 0;//当前光线射在哪面墙上
int flag = 1;
double dis = q;
double tan_angle = double(p) / q;
while (!reflect(wall, dis, tan_angle, p, flag));
return wall;
}
bool reflect(int &wall, double &dis, double &tan_angle,int &p,int &flag)
{
if (flag > 0)//逆时针
{
double a = (p - dis)*tan_angle;
if (abs(p - a) < 1e-6)
{
wall = (wall + 2) % 4;
return true;
}
if (abs(a) < 1e-6)
{
wall = (wall + 1) % 4;
return true;
}
if (a > p)//射到对面
{
wall = (wall + 2) % 4;
dis = p - dis - p / tan_angle;
flag = -flag;
}
if (a < p)//射到下一面
{
wall = (wall + flag) % 4;
tan_angle = 1 / tan_angle;
dis = a;
}
}
else//顺时针
{
double a = dis * tan_angle;
if (abs(p - a) < 1e-6)
{
wall = (wall + 3) % 4;
return true;
}
if (abs(a) <= 1e-6)
{
return true;
}
if (a > p)//射到对面
{
wall = (wall + 2) % 4;
dis = p - dis + p / tan_angle;
flag = -flag;
}
if (a < p)
{
wall = (wall + flag) % 4;
dis = p - a;
tan_angle = 1 / tan_angle;
}
}
return false;
}
后面看了题解才知道 可以用最小公倍数来做 可以上下无限延伸这个墙面 那么光线就一直在左右镜面中反射 每次横着走了p距离 纵着走了q距离 那么如果射到角落里面就要满足kq是p的倍数 也就是要找到最小的k 就是求q和p的最小公倍数
然后根据kq/p的奇偶来判断是最后射在了上面还是下面 奇则为射在了上面 偶则为射在了下面
根据k的奇偶性来判断是射在了左边还是右边 k为奇则是右边 k为偶则为左边
int gcd(int p, int q)
{
if (q == 0) return p;
else return gcd(q, p%q);
}
int mirrorReflection(int p, int q) {
int g = gcd(p, q);
int k = p / g;
if (k % 2)
{
if ((q / g) % 2)
{
return 1;
}
else
{
return 0;
}
}
else//k为偶
{
return 2;
}
}