. . 题意：一个L*W的矩形中有两个点，问起始点通过与墙壁n次碰撞后与另一个点碰撞的最短距离。 . . 解法：我的方法是每次碰撞起始就是一次对称（可以自己画一下图），我把矩形作n次合法的对称求出终点的对称点，再求所有可行解中两点距离的最小值。 . .
#include <iostream> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> using namespace std; const double eps = 1e-15; struct point { double x, y; bool operator==(point &other) { if (fabs(x-other.x) < eps && fabs(y-other.y) < eps) return true; return false; } bool operator!=(point &other) { if (*this == other) return false; return true; } }; bool flag[300][300]; point s, t, f[300][300]; double l, w; int k, n; double sqr(double x) { return x*x; } void dfs(int x, int y) { if (abs(x)+abs(y) > n) return; if (!flag[x+1+150][y+150]) { f[x+1+150][y+150].x = (x+1)*l*2-f[x+150][y+150].x; f[x+1+150][y+150].y = f[x+150][y+150].y; // if (f[x+150][y+150] != f[x+1+150][y+150]) { flag[x+1+150][y+150] = true; dfs(x+1, y); // } } if (!flag[x-1+150][y+150]) { f[x-1+150][y+150].x = x*l*2-f[x+150][y+150].x; f[x-1+150][y+150].y = f[x+150][y+150].y; // if (f[x+150][y+150] != f[x-1+150][y+150]) { flag[x-1+150][y+150] = true; dfs(x-1, y); // } } if (!flag[x+150][y+1+150]) { f[x+150][y+1+150].x = f[x+150][y+150].x; f[x+150][y+1+150].y = (y+1)*w*2-f[x+150][y+150].y; // if (f[x+150][y+150] != f[x+150][y+1+150]) { flag[x+150][y+1+150] = true; dfs(x, y+1); // } } if (!flag[x+150][y-1+150]) { f[x+150][y-1+150].x = f[x+150][y+150].x; f[x+150][y-1+150].y = y*w*2-f[x+150][y+150].y; // if (f[x+150][y+150] != f[x+150][y-1+150]) { flag[x+150][y-1+150] = true; dfs(x, y-1); // } } } bool check(int x, int y) { if (x > 0 && f[x+150][y+150] == f[x-1+150][y+150]) return false; if (x < 0 && f[x+150][y+150] == f[x+1+150][y+150]) return false; if (x > 0 && y > 0 && f[x+150][y+150] == f[x-1+150][y-1+150]) return false; if (x > 0 && y < 0 && f[x+150][y+150] == f[x-1+150][y+1+150]) return false; if (x < 0 && y < 0 && f[x+150][y+150] == f[x+1+150][y+1+150]) return false; if (x < 0 && y > 0 && f[x+150][y+150] == f[x+1+150][y-1+150]) return false; if (y > 0 && f[x+150][y+150] == f[x+150][y-1+150]) return false; if (y < 0 && f[x+150][y+150] == f[x+150][y+1+150]) return false; int kx = x>=0?1:-1; int ky = y>=0?1:-1; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (flag[150+kx*i][150+ky*j] && (x!=kx*i || y!=ky*j) && (f[150+kx*i][150+ky*j].x != f[150+x][150+y].x || f[150+kx*i][150+ky*j].y != f[150+x][150+y].y)) { double co = (f[150+kx*i][150+ky*j].x-s.x)*(f[150+x][150+y].x-s.x)+ (f[150+kx*i][150+ky*j].y-s.y)*(f[150+x][150+y].y-s.y); co = co/sqrt(sqr(f[150+kx*i][150+ky*j].x-s.x)+ sqr(f[150+kx*i][150+ky*j].y-s.y)); co = co/sqrt(sqr(f[150+x][150+y].x-s.x)+sqr(f[150+x][150+y].y-s.y)); if (fabs(co-1) <= eps) return false; } return true; } double cheng(point &t1, point &t2) { return (t1.x*t2.y-t1.y*t2.x); } int main() { freopen("f.in","r",stdin);freopen("f1.out","w",stdout); while (scanf("%lf %lf %lf %lf %lf %lf %d", &l, &w, &s.x, &s.y, &t.x, &t.y, &n) != EOF) { if (fabs(l+w+s.x+s.y+t.x+t.y+n) < eps) break; if (n == 0) { printf("%.3lf\n", sqrt(sqr(t.x-s.x)+sqr(t.y-s.y))); continue; } memset(f, 0, sizeof(f)); f[150][150].x = t.x; f[150][150].y = t.y; memset(flag, 0, sizeof(flag)); flag[150][150] = true; dfs(0, 0); double ans = 10000*(l+w); for (int i = 0; i < 300; i++) for (int j = 0; j < 300; j++) if (flag[i][j]) { int x = i-150; int y = j-150; if (abs(x)+abs(y) == n && check(x, y)) { double dist = sqrt(sqr(f[i][j].x-s.x)+sqr(f[i][j].y-s.y)); if (dist < ans) ans = dist; } } printf("%.3lf\n", ans); } } // -1 -1