In one key step of solving AtCoder Grand Contest 051, Problem E, one must solve the following subproblem (see the editorial for more information):
Given $$$n$$$ vectors $$$P_1, P_2, \cdots, P_n$$$, whose x- and y-components are integers, the set of vectors that can be expressed as $$$\Sigma w_iP_i$$$, where $$$w_i$$$ are arbitrary integers, can be expressed as {$$$mA + nB \mid m, n \in \mathbb{Z} $$$} (I understand why this is true), where $$$A$$$ and $$$B$$$ are some vectors. Find $$$A$$$ and $$$B$$$.
The editorial states that the problem can be solved using a "gcd-like algorithm", but I am struggling to figure out what the algorithm actually is. Can someone provide more details? This appears to be an interesting problem that can be useful for solving other problems as well.
It suffices to solve this problem with $$$n = 3$$$, because we can repeatedly add in one vector at a time. Given 3 vectors $$$P_1, P_2, P_3$$$, we can always find a pair such that $$$\lvert p \pm q \rvert < \max(\lvert p \rvert, \lvert q \rvert)$$$ (here, we use the Euclidean norm); this is because we must be able to find some pair of $$$\pm P_1, \pm P_2, \pm P_3$$$ which are at most 60 degrees apart. Thus, we can reduce the magnitudes of the vectors without changing the span, and all coordinates are integers, so it will eventually terminate with one of the vectors as $$$(0,0)$$$. Then, the other 2 are our basis.
To be more efficient, we should do multiple steps at a time, i.e. take $$$p + k q$$$ for the $$$k$$$ which minimizes $$$\lvert p + kq \rvert$$$. I don't have the proof, but I believe you can show this reduces the magnitudes by a factor of at least $$$2$$$ every several steps, so this runs in $$$\log MAX$$$ time.