UVA-10355 Superman 解題紀錄

🔗 UVA-10355 Superman

tags: CPE-241015 數學(Math)

題意

超人以極高的速度飛行。然而，他在飛行穿過大城市時遇到了一個困擾他的問題：有些區域的空氣污染嚴重，當他穿過這些區域時會很難呼吸，飛行速度也會顯著下降。他想知道自己經過這些污染區域的路徑長度。

每個污染區域的形狀都是球形。超人知道這些污染區域的位置，但不知道如何計算自己在這些區域內飛行的路徑長度，因此他請求你來幫忙計算。

給定超人飛行路徑的起點座標 $(x_1, y_1, z_1)$ 和終點座標 $(x_2, y_2, z_2)$，以及 $n$ 個污染區域的中心座標和半徑 $spheres_i = (x_i, y_i, z_i, r_i)$，要求計算超人飛行路徑中經過污染區域的百分比，精確到小數點後兩位。

約束條件

• $1 \leq n \leq 10$
• 題目保證每個污染區域不互相重疊。

思路：數學(Math)

由於超人飛行的路徑是直線，因此我們可以將問題轉換為計算直線與球體的交點，並計算超人飛行路徑中經過污染區域的百分比。

首先，將超人的飛行路徑從起點 $P_1 = (x_1, y_1, z_1)$ 到終點 $P_2 = (x_2, y_2, z_2)$ 進行參數化表示。令參數 $t$（$0 \leq t \leq 1$）代表從起點到終點的比例位置，則路徑上的任意點 $P(t)$ 可以表示為：

$$P(t) = P_1 + t \cdot (P_2 - P_1) = P_1 + t \cdot D$$

其中，$D = P_2 - P_1 = (D_x, D_y, D_z) = (x_2 - x_1, y_2 - y_1, z_2 - z_1)$ 是路徑的方向向量。

而球體的方程可以表示為：

$$||X - C||^2 = r_i^2$$

其中 $X = (x, y, z)$ 是路徑上的任意點，$C = (x_i, y_i, z_i)$ 是球體的中心，$r_i$ 是球體的半徑。

將 $P(t)$ 代入球體的方程，得到：

$$\begin{aligned} &||P(t) - C||^2 = r_i^2 \\ \Rightarrow \quad &||P_1 + t \cdot D - C||^2 = r_i^2 \\ \Rightarrow \quad &||P_1 - C + t \cdot D||^2 = r_i^2 \end{aligned}$$

令 $E = P_1 - C$ 是從起點到球心 $C$ 的向量代入，得到：

$$\begin{aligned} &||E + t \cdot D||^2 = r_i^2 \\ \Rightarrow \quad & E^2 + 2 \cdot E \cdot D \cdot t + D^2 \cdot t^2 = r_i^2 \\ \Rightarrow \quad & D^2 \cdot t^2 + 2 \cdot E \cdot D \cdot t + E^2 - r^2 = 0 \end{aligned}$$

令 $a = D^2$，$b = 2 \cdot E \cdot D$，$c = E^2 - r^2$，可以得到一個關於 $t$ 的二次方程：

$$a t^2 + b t + c = 0$$

接著，對於每個污染區域，我們需要利用二次方程的判別式 $\Delta = b^2 - 4ac$，計算路徑與球體的交點。

• 如果 $\Delta \leq 0$，表示路徑與球體不相交或相切，無需進一步處理。
• 如果 $\Delta > 0$，則計算兩個實根：

  $$t_1 = \frac{-b - \sqrt{\Delta}}{2a}, \quad t_2 = \frac{-b + \sqrt{\Delta}}{2a}$$

  • 由於 $t$ 的範圍在 $[0, 1]$ 之間，因此我們需要將 $t_1$ 和 $t_2$ 限制在 $[0, 1]$ 之間。
    • $t_1 = \max(0, t_1)$
    • $t_2 = \min(1, t_2)$
  • 如果 $t_1 \leq t_2$，則將 $t_1$ 和 $t_2$ 加入到交點列表 $intervals$ 中。
  • 將 $t_1$ 和 $t_2$ 限制在 $[0, 1]$ 之間，如果 $t_1 \leq t_2$，則將 $t_1$ 和 $t_2$ 加入到交點列表 $intervals$ 中。

最後，計算所有交點的長度，得到超人飛行路徑中經過污染區域的比例 $\displaystyle\sum_{i=1}^{m} (t_{\text{end}_i} - t_{\text{start}_i})$，其中 $m$ 是有效交點的數量。

• 由於題目確保每個污染區域不互相重疊，因此我們可以直接將所有交點的長度加總，否則需要合併區間，並改為計算重疊區間的長度。
• 由於答案需要為百分比，因此最後需要乘以 $100$。

複雜度分析

• 時間複雜度：$O(n)$，其中 $n$ 是污染區域的數量。
  • 對於每個污染區域，我們需要進行一次二次方程的求解，這是常數時間操作。因此，整體時間複雜度為 $O(n)$。
• 空間複雜度：$O(n)$。
  • 我們需要額外的空間來存儲每個污染區域的有效區間，最多需要 $O(n)$ 的空間。

PythonC++

import math

def dist2(P1, P2):
    return (P1[0] - P2[0]) ** 2 + (P1[1] - P2[1]) ** 2 + (P1[2] - P2[2]) ** 2

while True:
    try:
        name = input()
    except EOFError:
        break
    x1, y1, z1, x2, y2, z2 = map(int, input().split())
    P1 = (x1, y1, z1)
    P2 = (x2, y2, z2)
    D = (x2 - x1, y2 - y1, z2 - z1)

    n = int(input())
    spheres = [list(map(int, input().split())) for _ in range(n)]
    intervals = []
    for x, y, z, r in spheres:
        C = (x, y, z)
        E = (P1[0] - C[0], P1[1] - C[1], P1[2] - C[2])

        a = dist2(P1, P2)
        b = 2 * (E[0] * D[0] + E[1] * D[1] + E[2] * D[2])
        c = dist2(P1, C) - r * r

        delta = b * b - 4 * a * c
        if delta <= 0:
            continue
        sqrt_delta = math.sqrt(delta)
        t1 = (-b - sqrt_delta) / (2 * a)
        t2 = (-b + sqrt_delta) / (2 * a)
        t1 = max(0, t1)
        t2 = min(1, t2)
        if t1 <= t2:
            intervals.append((t1, t2))

    # intervals.sort()
    # merged = []
    # for l, r in intervals:
    #     if not merged or l > merged[-1][1]:
    #         merged.append([l, r])
    #     else:
    #         merged[-1][1] = r

    ans = 0
    for l, r in intervals:
        ans += r - l

    print(name)
    print(f"{ans * 100:.2f}")

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

struct Point {
    int x, y, z;
};

struct Sphere {
    Point c;
    int r;
};

double dist2(Point a, Point b) {
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) + (a.z - b.z) * (a.z - b.z);
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n;
    string name;
    Point P1, P2, D, E;
    while (cin >> name) {
        cin >> P1.x >> P1.y >> P1.z >> P2.x >> P2.y >> P2.z;
        D = {P2.x - P1.x, P2.y - P1.y, P2.z - P1.z};
        cin >> n;
        vector<Sphere> spheres(n);
        for (int i = 0; i < n; i++) {
            cin >> spheres[i].c.x >> spheres[i].c.y >> spheres[i].c.z >> spheres[i].r;
        }
        vector<pair<double, double>> intervals;
        for (auto &s : spheres) {
            E = {P1.x - s.c.x, P1.y - s.c.y, P1.z - s.c.z};
            double a = dist2(P1, P2);
            double b = 2 * (E.x * D.x + E.y * D.y + E.z * D.z);
            double c = dist2(P1, s.c) - s.r * s.r;
            double delta = b * b - 4 * a * c;
            if (delta <= 0) continue;
            double sqrt_delta = sqrt(delta);
            double t1 = (-b - sqrt_delta) / (2 * a);
            double t2 = (-b + sqrt_delta) / (2 * a);
            t1 = max(0.0, t1);
            t2 = min(1.0, t2);
            if (t1 <= t2) {
                intervals.emplace_back(t1, t2);
            }
        }

        // sort(intervals.begin(), intervals.end());
        // vector<pair<double, double>> merged;
        // for (auto &[l, r] : intervals) {
        //     if (merged.empty() || l > merged.back().second) {
        //         merged.emplace_back(l, r);
        //     } else {
        //         merged.back().second = max(merged.back().second, r);
        //     }
        // }

        double ans = 0;
        for (auto p : intervals) {
            ans += p.second - p.first;
        }
        cout << name << endl;
        cout << fixed << setprecision(2) << ans * 100 << endl;
    }
    return 0;
}

---

寫在最後

PROMPT

masterpiece, best quality, high quality, extremely detailed CG unity 8k wallpaper, extremely detailed, High Detail, vibrant colors, backlight, photo background,

(1girl, solo), Frieren, frieren, long hair, very long hair, (green eyes:1.5), grey hair, pointy ears, elf,

dress, white dress, sleeveless, sleeveless dress, jewelry, earrings, bare shoulders, parted bangs, bare arms, barefoot, bare legs, collarbone, looking at viewer, blush, sitting, closed mouth, full body, flower, water, wariza, strap slip, between legs, hand between legs, lily pad,

anime girl, sitting in water, white dress, pointed ears, floating flowers, serene, fantasy, soft lighting, dreamy atmosphere,