Dungeon

题目描述

The mission of space explorers found on planet M the vast dungeon. One of the dungeon halls is fill with the bright spheres. The explorers find out that the light rays reflect from the surface of the spheres according the ordinary law (the incidence angle is equal to the reflectance angle, the incidence ray, the reflected ray and the perpendicular to the sphere surface lay in the one plane). The ancient legend says that if the light ray will reflect from the spheres in the proper order, than the door to the room with very precious ancient knowledge will open. You are not to guess the right sequence; your task is much simpler. You are given the positions and the radii of the spheres, the place where the laser shot was made and the direction of light propagation. And you must find out the sequence in which the light will be reflected from the spheres.

题意概述

空间中有$N$个球，给定一条光线，光线在碰到球之后会发生反射，求光线碰到的前十个球。

数据范围：$1 \le N \le 50$。

算法分析

对每一次分别计算出光线碰到的第一个球，也就是沿光线方向距离最近的球。设球的半径为$r$，球心到光源的距离为$l$，球心到光线的距离为$d$，那么光线到球的距离等于$\sqrt{l^2-d^2}-\sqrt{r^2-d^2}$，其中$d$可以用三维叉积来计算。找到最近的球之后需要更新光源和光线方向，这些都可以用向量运算解决。

代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

static const long double EPS = 1e-10;
int cmp(long double t) { return fabs(t) < EPS ? 0 : t > 0 ? 1 : -1; }

struct Point {
  long double x, y, z;
  Point(long double _x = 0, long double _y = 0, long double _z = 0) : x(_x), y(_y), z(_z) {}
  Point operator + (const Point &a) const { return Point(x + a.x, y + a.y, z + a.z); }
  Point operator - (const Point &a) const { return Point(x - a.x, y - a.y, z - a.z); }
  Point operator * (const long double &a) const { return Point(x * a, y * a, z * a); }
  Point operator / (const long double &a) const { return Point(x / a, y / a, z / a); }
  Point operator * (const Point &a) const { return Point(y * a.z - z * a.y, z * a.x - x * a.z, x * a.y - y * a.x); }
  long double operator & (const Point &a) const { return x * a.x + y * a.y + z * a.z; }
  long double operator ! () const { return sqrt(x * x + y * y + z * z); }
  long double operator ^ (const Point &a) const { return (*this & a) / (! *this * ! a); }
};

struct Line {
  Point a, b;
  Line(Point _a = Point(), Point _b = Point()) : a(_a), b(_b) {}
  long double operator % (const Point &p) const { return ! ((b - a) * (p - a)) / ! (b - a); }
};

struct Ball { Point p; long double r; };

struct Solver {
private:
  static const int N = 50;
  int n;
  Point a, b;
  Ball ball[N];
  void input() {
    cin >> n;
    for (int i = 0; i < n; ++ i) cin >> ball[i].p.x >> ball[i].p.y >> ball[i].p.z >> ball[i].r;
    cin >> a.x >> a.y >> a.z >> b.x >> b.y >> b.z;
  }
  void process() {
    int p = -1, last = -1;
    for (int i = 0; i < 11; ++ i) {
      long double dis = 100000; p = -1;
      for (int j = 0; j < n; ++ j)
        if (j != last && ~ cmp((b - a) ^ (ball[j].p - a)) && ~ cmp(ball[j].r - Line(a, b) % ball[j].p)) {
          long double tmp = sqrt(abs(! (ball[j].p - a) * ! (ball[j].p - a) - (Line(a, b) % ball[j].p) * (Line(a, b) % ball[j].p))) - sqrt(abs(ball[j].r * ball[j].r - (Line(a, b) % ball[j].p) * (Line(a, b) % ball[j].p)));
          if (cmp(dis - tmp) == 1) dis = tmp, p = j;
        }
      if (! ~ p || i == 10) break; last = p;
      if (i) cout << ' '; cout << p + 1;
      Point c = a + (b - a) / ! (b - a) * dis;
      Point d = ball[p].p + (c - ball[p].p) / ! (c - ball[p].p) * (! (a - ball[p].p) * ((a - ball[p].p) ^ (c - ball[p].p)));
      b = d * 2 - a, a = c;
    }
    if (~ p) cout << " etc."; cout << endl;
  }

public:
  void solve() { input(), process(); }
} solver;

int main() {
  solver.solve();
  return 0;
}