分数: 100 点
问题陈述
DEGwer 拥有一块矩形土地 [-W, W] \times [-H, H] 在飞机上,他在那里从事农业。 他正遭受鸟类和野兽造成的伤害,他决定拉长梁来烧毁入侵他土地的生物。 具体来说,他将建造带有标志的柱子,或者 + or -,在他的土地上的整数网格点上,然后将梁拉伸为之间的一段 两根柱子有不同的标志。 但如果两根光束共用一个无柱点,那么光束能量共振就会发生可怕的事情,所以他必须让任意两根光束不共用一个无柱点。
DEGwer 已决定 N 整数网格点 (X_i, Y_i) \ (i = 1, 2, \dots, N) 他将在其上建造支柱。 这些网格点包括了他土地的四个角,并且这些网格点中的任何三个都不在一条线上。 您的任务是通过确定每个柱子的符号以及在哪些柱子之间拉伸梁来最大化拉伸梁的数量。
约束
- 1 \le W \le 10^9
- 1 \le H \le 10^9
- 4 \le N \le 10^5
- -W \le X_i \le W \ \ (1 \leq i \leq N)
- -H \le Y_i \le H \ \ (1 \leq i \leq N)
- (X_i, Y_i) \neq (X_j, Y_j) \ \ (i \neq j)
- 存在索引 i 这样 (X_i, Y_i) = (\pm W, \pm H) (对于任何一对标志)。
- 当 i \neq j \neq k \neq i, 三个网格点 (X_i, Y_i), (X_j, Y_j), 和 (X_k, Y_k) 不在一行上。
输入
输入由标准输入按以下格式给出:
W \ H N X_1 \ Y_1 X_2 \ Y_2 \vdots X_N \ Y_N
输出
按以下格式打印最大化拉伸梁数量的方法:
S M P_1 \ Q_1 P_2 \ Q_2 \vdots P_M \ Q_M
- S 是一个长度为的字符串 N 组成
+和-,其 i- 第一个字符 S_i 代表柱子的标志 i 构建于 (X_i, Y_i). - M 是拉伸梁的最大数量。
- 对于 i = 1, 2, \dots, M, 一对 (P_i, Q_i) 表示在柱子之间拉伸梁 P_i 和支柱 Q_i, 其中 S_{P_i} \neq S_{Q_i} 必然成立。
- 当 i \neq j, 之间的两个段 (X_{P_i}, Y_{P_i}) 和 (X_{Q_i}, Y_{Q_i}) 和之间 (X_{P_j}, Y_{P_j}) 和 (X_{Q_j}, Y_{Q_j}) 除了共同的端点外,不共享任何点。
示例输入 1
1 1 4 1 1 -1 1 -1 -1 1 -1
示例输出 1
+-+- 4 1 2 2 3 3 4 4 1
DEGwer 的土地是 [-1, 1] \times [-1, 1],他将在四个角上建造四个柱子。 如果您以(逆)时针方向为角柱分配交替符号,则可以在任何相邻柱之间拉伸梁,这是最大的。
示例输入 2
1 2 5 1 2 -1 2 0 1 -1 -2 1 -2
示例输出 2
+-++- 6 1 2 2 4 4 5 5 1 2 3 3 5
DEGwer 的土地是 [-1, 1] \times [-2, 2],他将在网格点上建造五个柱子 (0, 1) 除了四个角。 如果您以(逆)时针方向向角柱分配交替符号,并向角柱分配任意符号 (0, 1),您总共可以拉伸六个光束作为示例输出 2。 可以证明七根梁不能被拉伸,所以这是一个解决方案的例子。