说明

该程序用于计算台球桌上母球在恰好撞击指定次数的桌沿后击中目标球的最短路径距离。程序通过镜像反射的方法模拟球桌的边界反射，并计算所有可能的路径以找到最短距离。

算法标签

• 计算几何
• 镜像反射
• 最短路径

解题思路

1. 问题分析：母球需要在撞击指定次数的桌沿后击中目标球。通过镜像反射的方法，将球桌的边界反射扩展到无限平面中，将问题转化为在镜像平面中寻找直线路径的最短距离。
2. 输入处理：读取每个测试用例的球桌尺寸、母球和目标球坐标，以及需要撞击的桌沿次数。
3. 镜像反射：对于每个可能的反射次数组合（水平和垂直方向），生成镜像目标球的位置。
4. 路径检查：检查母球到镜像目标球的路径是否满足指定的反射次数，并且路径不被其他镜像球阻挡。
5. 距离计算：计算所有满足条件的路径的距离，并找出最短距离。

分析

• 镜像反射：通过水平和垂直方向的镜像反射，生成多个镜像目标球的位置，模拟球在桌沿的反射。
• 路径验证：确保路径上的反射次数与输入要求一致，并且路径是直线不被阻挡。
• 最短路径：在所有满足条件的路径中，选择欧几里得距离最短的路径。

实现步骤

1. 读取输入：循环读取每个测试用例，直到遇到全零输入。
2. 镜像反射处理：对于每个可能的反射次数组合（水平和垂直方向），生成镜像目标球的位置。
3. 路径验证：检查母球到镜像目标球的路径是否满足指定的反射次数，并且路径不被其他镜像阻挡。
4. 距离计算：计算所有有效路径的距离，记录最短距离。
5. 输出结果：格式化输出最短距离，保留三位小数。

代码解释

• 数据结构：
  • PoolTable类：封装台球桌问题的解决方法。
  • distance方法：计算两点之间的欧几里得距离。
  • collinear和between方法：检查三点是否共线以及一点是否在两点之间。
  • x和y方法：计算镜像反射后的坐标。
• 关键方法：
  • check方法：验证特定反射次数组合的路径是否有效，并更新最短距离。
  • doit方法：处理输入数据，调用check方法计算最短路径，并输出结果。
• 主函数：创建PoolTable对象并调用doit方法处理输入。

该程序通过镜像反射和几何计算，高效地解决了台球路径问题，适用于类似的反射路径计算场景。

代码

#include <iostream>
#include <cmath>
#include <iomanip>
#include <limits>  
#include <algorithm>  

using namespace std;

class PoolTable {
public:
    double distance(int x1, int y1, int x2, int y2) {
        double dx = x2 - x1;
        double dy = y2 - y1;
        return sqrt(dx * dx + dy * dy);
    }

    bool collinear(int ax, int ay, int bx, int by, int cx, int cy) {
        if (ay == by) {
            return (by == cy);
        } else if (ax == bx) {
            return (bx == cx);
        } else {
            return ((by - ay) * (cx - bx) == (cy - by) * (bx - ax));
        }
    }

    bool between(int x1, int y1, int x2, int y2, int x3, int y3) {
        bool xbetween = (x1 < x3) ? (x1 <= x2 && x2 <= x3) : (x3 <= x2 && x2 <= x1);
        bool ybetween = (y1 < y3) ? (y1 <= y2 && y2 <= y3) : (y3 <= y2 && y2 <= y1);
        return xbetween && ybetween && collinear(x1, y1, x2, y2, x3, y3);
    }

    int x(int over, int l, int xb) {
        return over * l + ((over & 1) ? l - xb : xb);
    }

    int y(int up, int w, int yb) {
        return up * w + ((up & 1) ? w - yb : yb);
    }

    void check(int up, int over, int xc, int yc, int l, int w, int xb, int yb, double& best) {
        int xr = x(over, l, xb);
        int yr = y(up, w, yb);
        
        int uplo = min(up, 0);
        int uphi = max(up, 0);
        int overlo = min(over, 0);
        int overhi = max(over, 0);
        
        bool unblocked = true;
        for (int u = uplo; u <= uphi && unblocked; u++) {
            for (int o = overlo; o <= overhi && unblocked; o++) {
                if (u != up || o != over) {
                    unblocked = !between(xc, yc, x(o, l, xb), y(u, w, yb), xr, yr);
                }
            }
        }
        
        if (unblocked) {
            best = min(best, distance(xc, yc, xr, yr));
        }
    }

    void doit() {
        int l, w, xc, yc, xb, yb, nbounces;
        while (cin >> l >> w) {
            if (l == 0 || w == 0) break;
            cin >> xc >> yc >> xb >> yb >> nbounces;
            
            double best = numeric_limits<double>::max();  // 修正此处的依赖
            
            for (int up = 0; up <= nbounces; up++) {
                int over = nbounces - up;
                check(up, over, xc, yc, l, w, xb, yb, best);
                check(-up, over, xc, yc, l, w, xb, yb, best);
                check(up, -over, xc, yc, l, w, xb, yb, best);
                check(-up, -over, xc, yc, l, w, xb, yb, best);
            }
            
            cout << fixed << setprecision(3) << best << endl;
        }
    }
};

int main() {
    PoolTable pt;
    pt.doit();
    return 0;
}