CF995C Leaving the Bar

对于一个向量 $\vec{v} = (x, y)$，定义 $|v| = \sqrt{x^2 + y^2}$。 Allen 在酒吧喝得有点多，酒吧位于原点。有 $n$ 个向量 $\vec{v_1}, \vec{v_2}, \cdots, \vec{v_n}$。Allen 将进行 $n$ 次移动。由于 Allen 的方向感受到了影响，在第 $i$ 次移动时，他要么沿着 $\vec{v_i}$ 的方向移动，要么沿着 $-\vec{v_i}$ 的方向移动。换句话说，如果他当前的位置为 $p = (x, y)$，他将移动到 $p + \vec{v_i}$ 或 $p - \vec{v_i}$。 Allen 不想离家（也就是酒吧）太远。你需要帮助他确定一组移动顺序（即每个向量的符号），使得他最终的位置 $p$ 满足 $|p| \le 1.5 \cdot 10^6$，以保证他的安全。

第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示移动的次数。 接下来的 $n$ 行，每行包含两个用空格分隔的整数 $x_i$ 和 $y_i$，表示 $\vec{v_i} = (x_i, y_i)$。保证对于所有 $i$，都有 $|v_i| \le 10^6$。

输出一行包含 $n$ 个整数 $c_1, c_2, \cdots, c_n$，每个整数为 $1$ 或 $-1$。如果 $p = \sum_{i = 1}^n c_i \vec{v_i}$ 满足 $|p| \le 1.5 \cdot 10^6$，你的方案就是正确的。 已知在给定的约束下，总是存在解。

由 ChatGPT 4.1 翻译