C. Leaving the Bar
brute force; data structures; geometry; greedy; math; sortings
For a vector \(\vec{v} = (x, y)\), define \(|v| = \sqrt{x^2 + y^2}\).Allen had a bit too much to drink at the bar, which is at the origin. There are \(n\) vectors \(\vec{v_1}, \vec{v_2}, \cdots, \vec{v_n}\). Allen will make \(n\) moves. As Allen's sense of direction is impaired, during the \(i\)-th move he will either move in the direction \(\vec{v_i}\) or \(-\vec{v_i}\). In other words, if his position is currently \(p = (x, y)\), he will either move to \(p + \vec{v_i}\) or \(p - \vec{v_i}\).Allen doesn't want to wander too far from home (which happens to also be the bar). You need to help him figure out a sequence of moves (a sequence of signs for the vectors) such that his final position \(p\) satisfies \(|p| \le 1.5 \cdot 10^6\) so that he can stay safe.
The first line contains a single integer \(n\) (\(1 \le n \le 10^5\)) — the number of moves.Each of the following lines contains two space-separated integers \(x_i\) and \(y_i\), meaning that \(\vec{v_i} = (x_i, y_i)\). We have that \(|v_i| \le 10^6\) for all \(i\).
Output a single line containing \(n\) integers \(c_1, c_2, \cdots, c_n\), each of which is either \(1\) or \(-1\). Your solution is correct if the value of \(p = \sum_{i = 1}^n c_i \vec{v_i}\), satisfies \(|p| \le 1.5 \cdot 10^6\).It can be shown that a solution always exists under the given constraints.