← 返回题目列表

Codeforces · 995/C

C. 离开酒吧

中文机器翻译题面 查看原题

对于向量 $$$\vec{v} = (x, y)$$$,定义 $$$|v| = \sqrt{x^2 + y^2}$$$。

艾伦在酒吧喝得有点多了,这是原点。有 $$$n$$$ 个向量 $$$\vec{v_1}、\vec{v_2}、\cdots、\vec{v_n}$$$。艾伦将做出 $$$n$$$ 动作。由于艾伦的方向感受损,在第 $$$i$$$ 次移动期间,他要么朝 $$$\vec{v_i}$$$ 方向移动,要么朝 $$$-\vec{v_i}$$$ 方向移动。换句话说,如果他当前的位置是 $$$p = (x, y)$$$,他将移动到 $$$p + \vec{v_i}$$$ 或 $$$p - \vec{v_i}$$$。

艾伦不想离家太远(碰巧也是酒吧)。您需要帮助他找出一系列移动(向量的符号序列),以便他的最终位置 $$$p$$$ 满足 $$$|p| \le 1.5 \cdot 10^6$$$ 这样他就可以保持安全。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 移动次数。

以下每一行包含两个空格分隔的整数 $$$x_i$$$ 和 $$$y_i$$$,表示 $$$\vec{v_i} = (x_i, y_i)$$$。我们有 $$$|v_i| \le 10^6$$$ 对于所有$$$i$$$。

输出

输出包含 $$$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$$$。

可以证明,在给定的约束条件下,解总是存在。

示例

输入 #1

3
999999 0
0 999999
999999 0

输出 #1

1 1 -1

输入 #2

1
-824590 246031

输出 #2

1

输入 #3

8
-67761 603277
640586 -396671
46147 -122580
569609 -2112
400 914208
131792 309779
-850150 -486293
5272 721899

输出 #3

1 1 1 1 1 1 1 -1