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