\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.99}}}}}\)

\(\color{#008b8b}{\text{Hướng dẫn trâu}}\)

• Với mỗi truy vấn thời gian, duyệt qua các thiên thạch và kiểm tra tại thời điểm \(t\) nó có tiếp cận trái đất không

\(\color{#008b8b}{\text{Tiếp cận trâu}}\)

• Tại thời điểm \(t\), thiên thạch đang ở vị trí \((x + v_x \times t, y + v_y \times t, z + v_z \times z)\)

• Khoảng cách từ trái đất ở \((0, 0, 0)\) đến thiên thạch là \(D = (x + v_x \times t)^2 + (y + v_y \times t)^2 + (z + v_z \times t)^2\)

• Khi khoảng cách \(D \leq R\) thì sẽ coi thiên thạch là nguy hiểm và tăng biến đếm

\(\color{#008b8b}{\text{Độ phức tạp trâu}}\)

• Mỗi thiên thạch ta có thể tính được giá trị trong \(O(1)\)

• Mỗi truy vấn phải duyệt qua các thiên thạch nên mất \(O(Q \times N)\)

\(\color{#008b8b}{\text{Hướng dẫn toán}}\)

• Nhận xét là bài toán chỉ gồm điểm ban đầu và gia tốc của từng biến không đổi nên khoảng cách sẽ càng gần trái đất rồi ra xa hơn.

• Vậy hàm khoảng cách \(f(t) = (x + v_x \times t)^2 + (y + v_y \times t)^2 + (z + v_z \times t)^2\) làm hàm lõm

• Nếu \(min(f(t)) \leq R\), hay phương trình giữa hình cầu và đường thẳng có nghiệm thì thiên thạch tiếp cận trong khoảng thời gian \([l, r]\) là đầu mút 2 nghiệm

• Nếu \(min(f(t)) > R\), hay phương trình giữa hình cầu và đường thẳng vô nghiệm thì thiên thạch không tiếp cận trái đất.

• Vậy với mỗi truy vấn \(t\), bài toán quy về đếm số thiên thạch có khoảng thời gian \([l, r]\) mà \(l \leq t \leq r\)

\(\color{#008b8b}{\text{Tiếp cận }}\)

• Giao điểm của đường thẳng \((x, y, z) \rightarrow (x + v_x, y + v_y, z + v_z)\) và hình cầu tâm \(O(0, 0, 0)\) bán kính \(R\) là

\((x + t \times v_x)^2 + (y + t \times v_y)^2 + (z + t \times v_z)^2 = R^2\)

\(\Leftrightarrow at^2 + 2b't + ct = 0\) trong đó:

• \(a = v_x^2 + v_y^2 + v_z^2\)
• \(b' = x \times v_x + y \times v_y + z \times v_z\)
• \(c = x^2 + y^2 + z^2 - R^2\)

Có \(\Delta' = b'^2 - ac\)

Khi \(\Delta' < 0\) thì thiên thạch không tiếp cận, ngược lại

• Nghiệm \(t_1 = \frac{-b'-\sqrt{\Delta'}}{a}\)
• Nghiệm \(t_2 = \frac{-b'+\sqrt{\Delta'}}{a}\)
• Đoạn \([t_1, t_2]\) là đoạn thời gian mà thiên thạch nguy hiểm với trái đất

• Gọi \(cnt_t\) là số thiên thạch có đoạn thời gian \([l, r]\) chứa \(t\)

Ban đẩu khởi tạo là \(cnt_p = 0\)

Vì truy vấn \(t \in \mathbb{N}\), với mỗi thiên thạch ta sẽ tăng các giá trị \(cnt_p\) lên \(1\) vói \((t_1 \leq p \leq t_2 \ \land \ p \in \mathbb{N})\)

• Thay vì chạy vòng for để ta cộng giá trị, ta có một trick đặc biệt:

Với mỗi đoạn \([l, r]\) ta cộng \(cnt_l\) lên \(1\) và trừ \(cnt_{r+1}\) xuống \(1\).

Sau đó biến nó thành mảng cộng dồn \(cnt_p = cnt_{p-1} + cnt_p\).

\(\color{#008b8b}{\text{Độ phức tạp}}\)

• Tính toán mất \(O(1)\) mỗi thiên thạch, mà có \(n\) thiên thạch tổng cộng là \(O(n)\)

• Tiền xử lí mất \(O(alphabet)\) duyệt lại qua mảng biến nó thành mảng cộng dồn

• Xuất kết quả mất \(O(1)\) mỗi truy vấn, mà có \(q\) truy vấn tổng cộng là \(O(q)\)

\(\color{#008b8b}{\text{Code tham khảo }}\): Toán, Quy hoạch động, Tiền xử lí, Giải trực tiếp

\(^{^{\color{purple}{\text{Độ phức tạp : }} O(n + q + alphabet)\ \color{purple}{\text{thời gian}}\ ||\ O(alphabet)\ \color{purple}{\text{bộ nhớ}}}}\)

#include <iostream>
#include <cmath>

using namespace std;

typedef long long ll;
const int LIM = 1e7 + 17;

int cnt[LIM];
int main()
{
    int n;
    ll R;
    cin >> n >> R;

    while (n-->0)
    {
        ll x, y, z, vx, vy, vz;
        cin >> x >> y >> z >> vx >> vy >> vz;

        ll a = vx * vx + vy * vy + vz * vz;
        ll b = x * vx + y * vy + z * vz;
        ll c = x * x + y * y + z * z - R * R;
        ll d = b * b - a * c;
        ll l =  ceil((-b - sqrt (d)) / a);
        ll r = floor((-b + sqrt (d)) / a);
        if (l < 0) l = 0;
        if (l <= r)
        {
            ++cnt[l];
            --cnt[r + 1];
        }
    }

    for (int x = 1; x < LIM; ++x)
        cnt[x] += cnt[x - 1];

    int q;
    cin >> q;

    while (q-->0)
    {
        int x;
        cin >> x;
        cout << cnt[x] << '\n';
    }
    return 0;
}