Description

  在一个 3D 游戏世界中，光线追踪要求计算光线与物体（如墙壁或障碍物）的相交，以实现视线检测、光影渲染等功能。为了提升游戏的性能和效果，你需要设计一个优化的光线追踪算法，目标是在保证精度的前提下，最小化计算时间。

  为简化问题，我们考虑 2D 世界由 N 个物体组成，每个物体可以是一个圆或一条线段。光线追踪算法需要处理从单个点发出的多条光线，并确定这些光线与场景中物体的第一次相交。

  给定一组光线，你的算法应计算每条光线与任何物体的第一次相交。如果光线未与任何物体相交，应返回适当的指示。

  本题的得分将由如下公式计算：

$$score = M^{1.1} \times N^{1.1} / time$$

  其中，$M$, $N$ 如题目格式所示，$time$ 为你的代码的运行毫秒数。

Format

  你的程序不需要也不要进行输入输出，只需要补充如下代码中函数的内容，后直接提交即可。

#include "RayTracing.h"


void RayTracing() {
    // 请在此处完成你的代码
}

double Circle::intersect(const Ray& ray) const {
    // 如果不需要这个函数，就不对其进行改动
    return Object::intersect(ray);
}

double Line::intersect(const Ray& ray) const {
    // 如果不需要这个函数，就不对其进行改动
    return Object::intersect(ray);
}

  物体存储在 objects 数组中，定义如下所示

vector<shared_ptr<Object>> objects;

// 你可以认为这等价于下面的定义
vector<Object*> objects;

  光线存储在 rays 数组中，定义如下所示

vector<Ray> rays;

  最后，你需要将结果存储在一个 map 中，其 key 代表光线的编号（从 0 开始），而 value 代表计算所得的最小距离（如果不存在则为-1），具体的存储方法见样例部分。

map<int, double> results;

  以上两个类型的定义见后文

  虽然你不需要进行输入输出，但可能需要了解输入的格式，以便于分析算法复杂度等问题

  输入包含多行：

• 第一行包含一个整数 $N$ ($1 ≤ N ≤ 10^5$)，表示场景中的物体数量。
• 接下来的 $N$ 行描述这些物体：
  • 每个物体由类型 (CIRCLE 或 LINE) 和该类型的特定参数组成：
    • CIRCLE 后面跟随圆心的坐标和半径。
    • LINE 后面跟随线段的两个端点坐标。
• 接下来的一行包含一个整数 $M$ ($1 ≤ M ≤ 10^5$)，表示需要追踪的光线数量。
• 接下来的 $M$ 行描述这些光线：
  • 每条光线由起点和方向向量描述。

  为了简化代码实现，题目提供了多种类型，如 Vector2 类型，表示一个二维的向量，其实现如下所示

struct Vector2 {
    double x, y;
    Vector2(double x = 0, double y = 0) : x(x), y(y) {}
    Vector2 operator-(const Vector2& v) const { return Vector2(x - v.x, y - v.y); }
    Vector2 operator+(const Vector2& v) const { return Vector2(x + v.x, y + v.y); }
    Vector2 operator*(double t) const { return Vector2(x * t, y * t); }
    double dot(const Vector2& v) const { return x * v.x + y * v.y; }
    double length() const { return sqrt(x * x + y * y); }
};

  Ray 类型实现如下所示，两个二维向量分别代表起点和方向向量

struct Ray {
    Vector2 origin, direction;
    Ray(Vector2 origin, Vector2 direction) : origin(origin), direction(direction) {}
};

  物体的定义如下所示

class Object {
public:
    virtual double intersect(const Ray& ray) const {
        return -1;
    }
};

class Circle : public Object {
public:
    Vector2 center;
    double radius;
    Circle(Vector2 center, double radius) : center(center), radius(radius) {}
    double intersect(const Ray& ray) const override;
};

class Line : public Object {
public:
    Vector2 p1, p2;
    Line(Vector2 p1, Vector2 p2) : p1(p1), p2(p2) {}
    double intersect(const Ray& ray) const override;
};

  使用方法举例

// 1 访问第 i 个物体
objects[i]

// 2 判断物体的类型
// 先判断是不是 Circle 类型，再判断是不是 Line 类型
for (auto obj : objects) {    
    if (auto circle = dynamic_pointer_cast<Circle>(obj)) {
        cout << "Circle radius: " << circle->radius << endl;
    } else if (auto line = dynamic_pointer_cast<Line>(obj)) {
        cout << "Line len: " << (line->p1 - line->p2).length() << endl;
    }
}

// 3 访问第 i 条光线的方向向量
rays[i].direction

// 4 写入第 i 条光线的计算结果，假设结果为 x
results[i] = x;

  如果你认为这些类型使得你的算法实现受阻，当然也可以将其转化为你自己的类型。

Samples

  提供一组输入数据用于自测，如果出现 Check failed 字样说明没有通过正确性检测

3
CIRCLE 0.0 0.0 5.0
LINE 10.0 0.0 10.0 10.0
LINE 5.0 5.0 10.0 5.0
2 
-10.0 0.0 1.0 0.0
-10.0 -10.0 1.0 1.0
5.000000
9.142136

  在这个例子中：

• 第一条光线 (-10, 0) 向 (1, 0) 方向，首先与圆形相交，距离为 5.000000。
• 第二条光线 (-10, -10) 向 (1, 1) 方向，首先与圆形相交，距离为 9.142136。

  对于这个例子的结果，应使得

results[0] = 5.000000
results[1] = 9.142136

  由于你不需要进行输入输出，因此只需要保证你的结果与标准答案的误差小于等于 $10^{-6}$ 即可。

Limitations

  对于所有测试点，有

$$N M \leq 10^9$$