作者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)