K - ± Beam Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

DEGwer さんは平面上の [-W, W] \times [-H, H] の土地を所有しており，ここで農業を営んでいます． 鳥獣被害に悩まされた DEGwer さんは，土地に侵入した動物を焼き払うビームを張り巡らせることにしました． 具体的には，土地内の格子点に + か - のいずれかの符号が付いた柱を立て，符号の異なる柱同士を結ぶ線分としてビームを張ります． ただし，ビーム同士が柱の無い点で交わると，ビームの持つエネルギーが共鳴して大変なことが起こるため，ビーム同士は柱の無い点を共有しないようにしなければなりません．

DEGwer さんは，柱を立てる N 個の格子点 (X_i, Y_i) \ (i = 1, 2, \dots, N) を既に決めています． その中には土地の四隅すべてが含まれ，さらに柱を立てるどの 3 点も同一直線上には存在しません． 各柱の符号とビームを張る柱のペアを適切に定めて，張るビームの数を最大にしてください．

制約

  • 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)
  • (X_i, Y_i) = (\pm W, \pm H)（複号任意）であるような i が存在する．
  • 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 は (X_i, Y_i) に立てる柱 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) の柱に任意の符号を割り当てることで，出力例のように 6 本のビームを張ることができます． また，7 本以上のビームを張れないことが証明できるので，これが最大であり答えの一例となります．

Score : 100 points

Problem Statement

DEGwer owns a rectangular land [-W, W] \times [-H, H] in the plane, and he is engaged in farming there. He is suffering from damage caused by birds and beasts, and he has decided to stretch beams that burn out creatures invading his land. Specifically, he will construct pillars having a sign, either + or -, on integer grid points in his land, and then stretch a beam as a segment between two pillars having different signs. However, if two beams share a point without a pillar, then something horrible happens because of resonance of beam energy, and hence he has to let any two beams not share a point without a pillar.

DEGwer has decided N integer grid points (X_i, Y_i) \ (i = 1, 2, \dots, N) on which he will construct the pillars. These grid points include the four corners of his land, and any three among these grid points are not on a single line. Your mission is to maximize the number of stretched beams by determining the sign of each pillar and between which pillars beams are stretched.

Constraints

  • 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)
  • There exists an index i such that (X_i, Y_i) = (\pm W, \pm H) (for any pair of signs).
  • When i \neq j \neq k \neq i, the three grid points (X_i, Y_i), (X_j, Y_j), and (X_k, Y_k) are not on a single line.

Input

The input is given from Standard Input in the following format:

W \ H
N
X_1 \ Y_1
X_2 \ Y_2
\vdots
X_N \ Y_N

Output

Print a way to maximize the number of stretched beams in the following format:

S
M
P_1 \ Q_1
P_2 \ Q_2
\vdots
P_M \ Q_M
  • S is a string of length N consisting of + and -, whose i-th character S_i represents the sign of the pillar i constructed on (X_i, Y_i).
  • M is the maximum number of stretched beams.
  • For i = 1, 2, \dots, M, the pair (P_i, Q_i) means to stretch a beam between the pillar P_i and the pillar Q_i, where S_{P_i} \neq S_{Q_i} necessarily holds.
  • When i \neq j, the two segments between (X_{P_i}, Y_{P_i}) and (X_{Q_i}, Y_{Q_i}) and between (X_{P_j}, Y_{P_j}) and (X_{Q_j}, Y_{Q_j}) do not share any point except for their common end points.

Sample Input 1

1 1
4
1 1
-1 1
-1 -1
1 -1

Sample Output 1

+-+-
4
1 2
2 3
3 4
4 1

DEGwer's land is [-1, 1] \times [-1, 1], and he will construct four pillars on the four corners. If you assign alternating signs to the corner pillars in (counter)clockwise direction, you can stretch a beam between any adjacent pillars, and this is maximum.

Sample Input 2

1 2
5
1 2
-1 2
0 1
-1 -2
1 -2

Sample Output 2

+-++-
6
1 2
2 4
4 5
5 1
2 3
3 5

DEGwer's land is [-1, 1] \times [-2, 2], and he will construct five pillars on the grid point (0, 1) in addition to the four corners. If you assign alternating signs to the corner pillars in (counter)clockwise direction and an arbitrary sign to the pillar on (0, 1), you can stretch six beams in total as Sample Output 2. It can be proved that seven beams cannot be stretched, so this is an example of a solution.