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

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

問題簡意

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

解題大方向步驟

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

各步驟詳解

輸入值以以下的值為例

CD 30 1
DB 30 1

① 展開正四面體

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

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

→

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

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

② 決定前進方向

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

由於套用 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)

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

＜毛毛蟲①＞

(-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

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

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

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

於是根據線性變換公式，把以 [(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 之間了，因此不需要計算。

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

⑦ 把會落在哪個點算出來

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

面	條件
① △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)
- 沒有字串長度或是陣列長度這一類的處理，因此把它歸為常數。

以上。