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

[tkcn (小安)]

※ 引述《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:為什麼可以視為加上任意選轉後的C @@??
先加 C 在旋轉，其實等於旋轉後的 A 加上旋轉後的 C。
※ 編輯: tkcn            來自: 140.114.78.231       (08/05 18:33)
推 singlovesong:好像瞭解了！ 不過你說的這一點我一直沒辦法說服自己
→ singlovesong:不知道如何證明..   謝謝你:)
推 LPH66:證明很簡單  你只要知道旋轉是線性變換即可
→ firejox:用擴展歐基里德應該可以判斷...
推 singlovesong:願聞其詳QQ
→ Favonia:後面面積那邊不太準吧（？）可能其實是 .5*c1 + 100*c2
→ firejox:A的部份是固定的 B也是固定的 所以先B-A
→ firejox:所以只要判斷C1 C2的分別的(X,Y)GCD 是否可以整除B-A的(X,
→ firejox:Y)的GCD即可
→ firejox:用解二元一次方程式的公式也可以...
→ Favonia:啊...我沒有仔細看內文。不好意思推了不相干的東西 orz
解法本來就不只一種 :p
不過目前我說的這種解法複雜度是 O(1)，並且只需要整數運算。
※ 編輯: tkcn            來自: 59.115.130.139       (08/06 11:44)