PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] 偏數學的問題

看板Prob_Solve (計算數學 Problem Solving)作者tkcn (小安)時間13年前 (2011/08/05 15:45)推噓4(4推 0噓 8→)

留言12則, 4人參與討論串2/2 (看更多)

※ 引述《singlovesong (~"~)》之銘言： : 給三個2D向量 A , B , C : 其中坐標皆為整數 : 其中 A 可以在任何時間點任意做下面兩件事情 : 1. 正時鐘方向旋轉 90 度 : 2. 加上 vector C : 請問A 能不能經由任意次數這樣子的operation 變成 B ? : 例如: A B C = (0,0) (1,1) (0,1) : answer = YES ((A + C)轉90 + C )= B : 例如： A B C = (0,0) (1,1) (2,2) : answer = NO : 請問數學原理是什麼要怎麼做呢？ : 謝謝這不是昨晚的 codeforces 嗎 XD 操作 (1) 可以將 A 旋轉出(最多) 4 個向量，命名為 A_i (0 <= i < 4)。而操作 (2)，因為操作 (1) 的關係，其實可以視為加上任意旋轉後的 C，旋轉後的 C 同樣也是(最多) 4 個，而且兩兩相反，所以留下其中兩個互相垂直的即可，命名為 C_1 與 C_2。接下來的問題就是，對 A 旋轉後的每一個向量 A_i，檢查加上任意個 C_1 與 C_2，能否到達 B。因為 C_1 與 C_2 是互相垂直的(不考慮 C=0 的情況)，所以必定能找到唯一一組 j, k 使得: A_i + j*C_1 + k*C_2 = B 然後只要驗證 j 與 k 是否為整數即可。若要驗證 j 是否為整數。可先求出 (B, A_i, A_i+C2) 所圍出的平行四邊形面積。(利用外積可輕易求出) "面積除以 C_2 的長度" 即為 "此平行四邊形以 C_2 為底的高"，(這條高會與 C_1 平行) 再檢查 "高" 是否為 "C_1 長度" 的整數倍即可。 C_1, C_2 長度其實是一樣的，所以其實只要檢查面積是否為 C 長度平方的整數倍即可。沒有圖實在很難說明呀，希望你能看懂 Q_Q 另外這裡有一堆神人寫的 code 可以參考。 (Problem C) http://www.codeforces.com/contest/101/standings -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.114.78.231

推

singlovesong

08/05 18:23, , 1^F

08/05 18:23, 1^F

先加 C 在旋轉，其實等於旋轉後的 A 加上旋轉後的 C。 ※ 編輯: tkcn 來自: 140.114.78.231 (08/05 18:33)

推

singlovesong

08/05 18:40, , 2^F

08/05 18:40, 2^F

→

singlovesong

08/05 18:40, , 3^F