LoginSignup
1
0

More than 3 years have passed since last update.

@vc7(Lihsuan CHEN)

Rendezvous on a Tetrahedron - 解法詳解，Swift 實作（中文）

Last updated at Posted at 2020-04-15

日本語版は後ほどアップさせていただきます。

題目： https://onlinejudge.u-aizu.ac.jp/problems/1384

問題簡意

有兩隻毛毛蟲在正四面體上爬行，都從頂點 A 以夾角 d 的方向出發，爬行到鄰接面的時候爬行方向和鄰接邊夾角不會改變，求兩隻毛毛蟲爬了一段距離 l 後停下來所在的面是不是在同一個。是則回傳字串 YES 否則回傳字串 NO 。

解題大方向步驟

  1. 把四面體展開成一個大三角型，以 A 為 (0,0) 在直角坐標中無限鋪開，會形成無數個正的正大三角形和反的正大三角形。在這裡把正的和反的組合起來成為一個平行四邊形。
  2. 由於最後想要把爬行位置正規化到第一象限的第一個平行四邊形，因此把爬行位置都往第三和第四象限延伸，這樣可以讓後續的計算比較好處理。
  3. 將兩隻毛毛蟲在第三或第四象限中的終點算出來。
  4. 第一步的正規化：把點移動到第一象限和第二象限裡面第一行的平行四邊形中。移動方式是移動到自己右上的那一組平行四邊形。
  5. 算出平行四邊形投影到正方形的線性變換矩陣，接著套到 (4.) 移動後的座標。
  6. 把各自的 x 座標橫向移動到第一象限第一組的平行四邊形
  7. 根據 (6) 取得的座標，就可以算出會落在哪個三角形
  8. 根據 (7) 取得的結果，回傳兩者是否相同

各步驟詳解

輸入值以以下的值為例

CD 30 1
DB 30 1

① 展開正四面體

這一段是來定下解題和思考方式的基礎。

在紙面上試著畫畫看就會發現直接對四面體運算無法解決。接著透過題目給的條件，就可以知道可以把三角形展開來思考。為了處理方便，我們把出發點的 A 放在座標軸 (0,0) 的位置上

image.png → image.png

由於進到另外一個面之後行進方向不會改變，就會發現毛毛蟲的路徑在攤開的平面上會是直線，如下圖所示。這時候也會發現結束的點不只可能會在正的大正三角形上，也有可能會落在反的大正三角形裡面。

image

以正反大三角形為一組成為一個平行四邊形，對無限攤開的座標上色之後，會如下圖。
我們最後會期望把點正規化到在第一象限、接著原點的藍色平行四邊形裡面。

image

② 決定前進方向

image

基於我們的平行四邊形移動方式是不斷往右上移動，因此我們會想讓初始的位置都落在第三和第四象限。

由於套用 cos, sin 時需要用 正向角 ，因此各自的方向向量從 0 開始計算，而移動的方向角如下：

vector AD = 360˚
vector AB = 300˚
vector AC = 240˚

於是實際的移動方向會是 「vector - θ」

這邊的 θ 就是題目中提到的 d ，為了好理解這邊用 θ 表示。

③ 計算原始的移動終點

  • angle = vector - θ

l 是題目給的移動長度

根據式子和題目給的條件，算出的終點位置是 (l * cos(angle), l * sin(angle))

註： cos 可求鄰邊，也就是 x 軸上的位置；而 sin 則可求對邊，也就是 y 軸上的位置

根據這個式子，兩隻毛毛蟲的最後位置會如下：

＜毛毛蟲①＞

CD 30 1 -> (AC) 240˚ - 30˚ = 210˚ -> (l * cos(angle), l * sin(angle)) = (-sqrt(3)/2, -1/2)

＜毛毛蟲②＞

DB 30 1 -> (AD) 360˚ - 30˚ = 330˚ -> (l * cos(angle), l * sin(angle)) = (sqrt(3)/2,- 1/2)

④ 正規化到第一、二象限中的第一行平行四邊形群

第一和第二象限的第一行平行四邊形群為止移動 (也就是 y 會 >= 0)
以單位邊長為 1 ，三角形的高便會是 sqrt(3)/2 ，移動到上面緊鄰的四邊形中同樣位置的 y 軸距離的算法是 sqrt(3)/2 * 2 = sqrt(3))

因此各自的移動距離如下，示意則如圖

  • x += 1
  • y += sqrt(3)

image

接下來就來移動我們的毛毛蟲吧！

＜毛毛蟲①＞

(-sqrt(3)/2, -1/2) -> (-sqrt(3)/2+1, -1/2+sqrt(3))

＜毛毛蟲②＞

(sqrt(3)/2,-1/2) -> (sqrt(3)/2+1,-1/2+sqrt(3))

而運算過程我傾向先不要把他們簡化，這比較算是個人的選擇 XDDD

⑤ 找出線性變換矩陣，並套到 ④ 中正規化之後的點

image

由於要判斷在哪個正三角形中，直接用正三角形找的話計算過程會變得異常複雜。於是這裡我們就要做如上圖的變換，把我們要面對的問題簡化。

而得出來的線性變換矩陣去對 ④ 算出來的座標運算之後，就會變換到正方形中相對的位置。這樣就比較好判斷到底是落在哪一個三角形中。

於是根據線性變換公式，把以 [(0,0),(1,2),(3,2),(2,0)] 圍起來的四邊形往 [(0,0),(0,2),(2,2),(2,0)] 圍成的正方形投影的線性變化矩陣如下。

註：需要取兩個點變化前後的座標才可以解出變換公式中的 a, b, c, d 等係數

這邊就不贅述該怎麼算線性變換矩陣（高中數學中通常叫他 A），可以自行去搜尋。或是參考這個 YouTube 影片，這位老師其實說明的還滿清楚的： https://www.youtube.com/watch?v=V4POGsNaAd8

得出線性變換矩陣如下（請原諒我不知道怎麼打矩陣出來）：

1  -1/sqrt(3)  →  a  b
0   2/sqrt(3)  →  c  d

接著就來更新我們毛毛蟲的位置吧，怎麼運算也可以參考上面貼的 YouTube 影片。

公式：

  • newX = ax + by
  • newY = cx + dy

＜毛毛蟲①＞ (-sqrt(3)/2+1, -1/2+sqrt(3))

  • newX = 1 * (-sqrt(3)/2 + 1) + -1/sqrt(3) * (-1/2+sqrt(3)) = -sqrt(3)/3 ~= -0.577
  • newY = 0 * (-sqrt(3)/2 + 1) + 2/sqrt(3) * (-1/2+sqrt(3)) = (6-sqrt(3))/3 ~= 1.423

＜毛毛蟲②＞ (sqrt(3)/2+1, -1/2+sqrt(3))

  • newX = 1 * (sqrt(3)/2 + 1) + -1/sqrt(3) * (-1/2+sqrt(3)) = 2 * sqrt(3) / 3 ~= 1.547
  • newY = 0 * (sqrt(3)/2 + 1) + 2/sqrt(3) * (-1/2+sqrt(3)) = (6-sqrt(3))/3 ~= 1.423

⑥ 移動到第一象限上的第一個大正方形

由於需要判斷落在哪一個面上， 還必須要把 x 移動到 0 < x < 2 之間（這時候 y 已經是在 0 到 2 之間了），由於移動到隔壁的正方形中同樣的位置的 x 軸差是 2 ，因此如果 x 大於 2 則不斷 -2 直到落到範圍之間，反之 x 小於 0 的話，則不斷 +2 直到進入範圍。當已經在範圍內的話，就不需要再做加減運算。

＜毛毛蟲①＞ (-sqrt(3)/3, (6-sqrt(3))/3) ~= (-0.577, 1.423)

(-sqrt(3)/3, (6-sqrt(3))/3) -> (-sqrt(3)/3 + 2, (6-sqrt(3))/3) ~= (1.423, 1.423)

＜毛毛蟲②＞ (2 * sqrt(3) / 3, (6-sqrt(3))/3) ~= (1.547, 1.423)

毛毛蟲② 的 x 軸已經在 0 到 2 之間了，因此不需要計算。

為了下個步驟方便，這邊就把各自大約的值算出來了。

⑦ 把會落在哪個點算出來

image

上圖對應的面和條件如下表

面 條件
① △ACD x < 1, y < 1, x + y < 1 x > 1, y > 1, (x-1) + (y -1) > 1
② △BCD x < 1, y < 1, x + y > 1 x > 1, y > 1, (x-1) + (y -1) < 1
③ △ABD x < 1, y > 1, x + (y-1) > 1 x > 1, y < 1, (x-1) + y < 1
④ △ABC x < 1, y > 1, x + (y-1) < 1 x > 1, y < 1, (x-1) + y > 1

來求各自的面：

＜毛毛蟲①＞ (-sqrt(3)/3 + 2, (6-sqrt(3))/3) ~= (1.423, 1.423) → ② △BCD

＜毛毛蟲②＞ (2 * sqrt(3) / 3, (6-sqrt(3))/3) ~= (1.547, 1.423) → ② △BCD

⑧ 把比較後的結果回傳

＜毛毛蟲①＞ ② △BCD
＜毛毛蟲②＞ ② △BCD

因為兩隻毛毛蟲都落在 ② △BCD ，所以根據題目要求回傳 YES 。

程式語言的三角函數運算

程式語言的三角函數運算接受的參數都 必須 要是「弧角」 (radian) 而不是角度，因此在運算之前，需要多一步把角度轉換成弧角。

  • radian = angle * (pi/180.0)

程式碼

import Foundation

// MARK: - Implementation

enum Face: Int {
    case unkown = -1
    case acd = 1
    case bcd = 2
    case abd = 3
    case abc = 4
}

/// 算出單一毛毛蟲最終位置的面的方法
func findFace(edge: String, degree: Double, length: Double) -> Face {
    let pi = Double.pi
    let sqrt3 = sqrt(3)

    let startVertex = String(edge[edge.startIndex])
    var radian: Double!

    // ② 決定前進方向
    switch startVertex {
    case "D": // "D", 360˚
        radian = (360 - degree) * (pi/180.0)
    case "B": // "B", 300
        radian = (300 - degree) * (pi/180.0)
    default:  // "C", 240˚
        radian = (240 - degree) * (pi/180.0)
    }

    // ③ 計算原始的移動終點
    var x = length * cos(radian)
    var y = length * sin(radian)

    // ④ 正規化到第一、二象限中的第一行平行四邊形群
    while y < 0 {
        x += 1
        y += sqrt3
    }

    // ⑤ 找出線性變換矩陣，並套到 ④ 中正規化之後的點
    var newX = x * 1 + y * (-1/sqrt3)
    let newY = x * 0 + y * (2/sqrt3)

    // ⑥ 移動到第一象限上的第一個大正方形
    while newX <= 0 { newX += 2 }
    while newX >= 2 { newX -= 2 }

    // ⑦ 把會落在哪個點算出來
    if newX < 1 && newY < 1             { return (newX     + newY     < 1) ? .acd : .bcd }
    if newX < 1 && 1 < newY && newY < 2 { return (newX     + newY - 1 < 1) ? .abc : .abd }
    if 1 < newX && newX < 2 && newY < 1 { return (newX - 1 + newY     < 1) ? .abd : .abc }
    if 1 < newX && 1 < newY && newY < 2 { return (newX - 1 + newY - 1 < 1) ? .bcd : .acd }

    return .unkown
}


// MARK: - Main Method

func isAtDifferenceFaces(lines: [String]) -> String {
    // 先簡單的處理輸入值，接著執行找面的方法
    let results = lines
        .map { $0.components(separatedBy: " ") }
        .map { (edge: $0[0], degree: Double($0[1])!, length: Double($0[2])!) }
        .map { findFace(edge: $0.edge, degree: $0.degree, length: $0.length) }

    // ⑧ 把比較後的結果回傳
    return results[0] == results[1] ? "YES" : "NO"
}

執行和驗證

佈置 test cases

/// Test cases from the problem
let sources = [
    ["CD 30 1", "DB 30 1"],
    ["BC 1 1", "DB 59 1"],
    ["BC 29 20", "BC 32 20"]
]

執行並驗證結果

let results = sources.map(isAtDifferenceFaces(lines:))

if results == ["YES", "YES", "NO"] {
    print("Passed")
} else {
    print("Failed")
}

複雜度分析

  • 令一毛毛蟲為 P, 爬行長度 lp 後的原始座標 Y 軸是 Yp, Y 軸正規化後的 X 軸是 Xp
  • 令另一毛毛蟲為 Q, 爬行長度 lq 後的原始座標 Y 軸是 Yq, Y 軸正規化後的 X 軸是 Xq

則

  • 時間複雜度： O(max(Yp/sqrt(3), Yq/sqrt(3), Xp/2, Xq/2) 簡化後為 O(max(Yp, Yq, Xp, Xq))
    • 算法就是單純取出有跑 loop 的地方，因為所有迴圈都沒有互相隸屬，所以直接從中取最大值即可。
  • 空間複雜度：O(1)
    • 沒有字串長度或是陣列長度這一類的處理，因此把它歸為常數。

以上。

1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
0