A - RectJoin /

Time Limit: 5 sec / Memory Limit: 1024 MB

### 問題文

RectJoin は正方形の方眼紙と鉛筆を使って遊ぶ以下のような一人プレイゲームである。

i 回目の操作では、まだ印の付けられていない格子点 p_{i,1} と、既に印の付けられている3つの格子点 p_{i,2}, p_{i,3}, p_{i,4} であって、以下の3つの条件を全て満たすものを選ぶ。

1. p_{i,1} p_{i,2} p_{i,3} p_{i,4} をこの順番に結ぶと軸に平行、もしくは45度傾いた長方形となる。
2. この長方形の外周上には p_{i,2}, p_{i,3}, p_{i,4} 以外に印の付いた格子点は存在しない。
3. この長方形の外周は、既に方眼紙に描かれている長方形の外周と正の長さの共通部分を持たない(いくつかの点で交わることは許される)。

$\mathrm{round}\left(10^6 \cdot\frac{N^2}{M}\cdot\frac{\sum_{(x, y)\in Q} w(x, y)}{S}\right)$

の得点が得られる。 出来るだけ高得点が得られるようにゲームをプレイするプログラムを作成せよ。

#### ルールの補足

• p_{i,1} は方眼紙の内部、すなわち、x 座標と y 座標がともに 0 以上 N-1 以下の範囲から選択しなければならない。
• p_{i,1} として選択した格子点は印が付くため、j(>i) 回目の操作で p_{j,1} として再度選択することは出来ないが、p_{j,k} (k=2,3,4) として再度選択することは出来る。
• p_{i,k} (k=2,3,4) も同様に、j(>i) 回目の操作で p_{j,k'} (k'=2,3,4) として繰り返し何度も選択出来る。
• 条件2にあるように、選んだ長方形の外周に他の印があってはならないが、逆に、既に描かれている長方形の外周上の点を p_{i,1} として選択して印を付けることは可能である。

#### テストケース数

• 暫定テスト: 50個
• システムテスト: 2000個、コンテスト終了後にseeds.txt (sha256=907b41fcba240515612a21798a10b0df7dda744b1268b74b3bbd41b93a73095e) を公開
• システムテストは N=31,33,35,\cdots,61 の入力をそれぞれ125個ずつ含む。
• seed=0 の入力は手動で作成されたものであり、暫定テスト、システムテストには含まれない。

### 入力

N M
x_1 y_1
\vdots
x_M y_M

• N は方眼紙の縦横の格子点の数を表す、31 以上 61 以下の奇数である。
• M は初期状態で印の付いている格子点の個数を表す、N 以上 \lfloor N^2/12 \rfloor 以下の整数である。
• (x_1, y_1), \cdots, (x_M, y_M) は 初期状態に置ける M 個の印の付いた格子点の座標を表し、\lfloor N/4\rfloor\leq x_i,y_i\leq\lfloor 3N/4\rfloor を満たす。

### 出力

K
x_{1,1} y_{1,1} x_{1,2} y_{1,2} x_{1,3} y_{1,3} x_{1,4} y_{1,4}
\vdots
x_{K,1} y_{K,1} x_{K,2} y_{K,2} x_{K,3} y_{K,3} x_{K,4} y_{K,4}


4点の順番は時計回りでも反時計回りでも良いが、(x_{i,1}, y_{i,1}) が新たに印を付ける点でなければならない。

### 入力生成方法

seed=0 の入力は手動で作成されたものであり、暫定テスト、システムテストには含まれない。 L 以上 U 以下の整数値を一様ランダムに生成する関数を \mathrm{rand}(L,U) で表す。

#### N, M の生成

N=\mathrm{rand}(15, 30)\times 2 + 1M=\mathrm{rand}(N, \lfloor N^2/12 \rfloor) により生成される。

#### (x_i, y_i) の生成

\lfloor N/4\rfloor\leq x,y\leq\lfloor 3N/4\rfloor を満たす格子点 (x,y) の中からランダムに M 個が選択される。

### ツール(入力ジェネレータ・ビジュアライザ)

コンテスト期間中に、seed=0 に対するビジュアライザの出力画像(PNG)のみ twitter で共有が可能です。動画形式での共有は禁止されているのでご注意下さい。 必ず指定されたハッシュタグを用い、公開アカウントを使用して下さい。共有出来るのはseed=0に対するビジュアライズ結果と点数のみで、GIF動画や出力文字列、他のシードでの点数の共有や、解法・考察に関する言及は禁止です。

### 入力例 1

33 58
13 24
14 24
15 24
16 24
17 24
12 23
18 23
11 22
19 22
10 21
20 21
9 20
21 20
8 19
15 19
18 19
22 19
8 18
12 18
15 18
18 18
22 18
8 17
12 17
15 17
18 17
22 17
8 16
12 16
15 16
18 16
22 16
8 15
12 15
15 15
18 15
22 15
9 14
12 14
15 14
18 14
21 14
10 13
12 13
15 13
18 13
20 13
22 13
11 12
12 12
15 12
18 12
19 12
23 12
12 11
15 11
18 11
24 11


### 出力例 1

20
9 15 12 12 15 15 12 18
15 20 12 17 15 14 18 17
23 22 19 22 19 12 23 12
23 14 22 15 21 14 22 13
10 14 10 13 12 13 12 14
11 11 12 11 12 12 11 12
18 20 15 20 15 19 18 19
19 16 22 19 21 20 18 17
12 19 12 18 15 18 15 19
15 22 12 19 15 16 18 19
14 22 15 22 15 24 14 24
15 8 18 11 15 14 12 11
10 15 9 15 9 14 10 14
11 18 12 19 10 21 9 20
22 23 20 21 21 20 23 22
21 15 18 15 18 14 21 14
15 26 13 24 15 22 17 24
20 20 16 24 14 22 18 18
21 17 18 20 15 17 18 14
11 14 10 13 11 12 12 13


### Problem Statement

RectJoin is the following single-player game played with square grid paper and pencil.

Let (0, 0) be the coordinates of the lower left corner of the grid paper, with the x-axis to the right and the y-axis to the top. The coordinates of the upper right corner of the grid paper are (N-1, N-1). Initially, M dots are placed on grid points, and you can repeat the following operations as many times as possible to place dots and draw rectangles on the grid paper.

In the i-th operation, choose a grid point p_{i,1} not containing a dot and three grid points p_{i,2}, p_{i,3}, p_{i,4} containing dots, which satisfy all of the following three conditions.

1. Connecting p_{i,1} p_{i,2} p_{i,3} p_{i,4} in this order forms a rectangle that is parallel to the axis or inclined at 45 degrees.
2. There are no dots other than p_{i,2}, p_{i,3}, p_{i,4} on the perimeter of this rectangle.
3. The perimeter of this rectangle does not share a common segment of positive length with the perimeter of an already drawn rectangle (intersecting at some points is allowed).

For the chosen four points, place a new dot on p_{i,1} and draw the perimeter of the rectangle p_{i,1} p_{i,2} p_{i,3} p_{i,4} on the grid paper.

Let (c,c)=((N-1)/2,(N-1)/2) be the coordinates of the center of the graph paper. We define the weight of each grid point as w(x,y)=(x-c)^2 + (y-c)^2 + 1 using the distance from the center. Let S=\sum_{x=0}^{N-1}\sum_{y=0}^{N-1} w(x,y) be the sum of the weights of all grid points. Let Q be the set of coordinates with dots in the final state (including the initially placed dots). Then you will get the following score.

$\mathrm{round}\left(10^6 \cdot\frac{N^2}{M}\cdot\frac{\sum_{(x, y)\in Q} w(x, y)}{S}\right)$

Create a program to play the game to get as high a score as possible.

#### Additional explanation of the rules

• You must choose p_{i,1} from the interior of the grid paper, i.e., from coordinates satisfying 0\leq x,y\leq N-1.
• Since a dot is placed on the grid point chosen as p_{i,1}, it cannot be chosen again as p_{j,1} in j(>i)-th operation, but it can be chosen again as p_{j,k} (k=2,3,4).
• Similarly, p_{i,k} (k=2,3,4) can be repeatedly chosen as p_{j,k'} (k'=2,3,4) in j(>i)-th operation.
• As stated in condition 2, there must be no other dots on the perimeter of the chosen rectangle, but conversely, you can choose a point on the perimeter of an already drawn rectangle as p_{i,1} and place a dot on it.

#### Number of test cases

• Provisional test: 50
• System test: 2000. We will publish seeds.txt (sha256=907b41fcba240515612a21798a10b0df7dda744b1268b74b3bbd41b93a73095e) after the contest is over.
• System test contains 125 inputs for each of N=31,33,35,\cdots,61.
• The input of seed=0 is manually created and is not included in the provisional or system test.

The score of a submission is the total scores for each test case. In the provisional test, if your submission produces illegal output or exceeds the time limit for some test cases, the submission itself will be judged as WA or TLE , and the score of the submission will be zero. The final ranking will be determined by the system test with more inputs which will be run after the contest is over. In the system test, if your submission produces illegal output or exceeds the time limit for some test cases, only the score for those test cases will be zero. The system test will be performed only for the last submission which received a result other than CE . Be careful not to make a mistake in the final submission.

#### About execution time

Execution time may vary slightly from run to run. In addition, since system tests simultaneously perform a large number of executions, it has been observed that execution time increases by several percent compared to provisional tests. For these reasons, submissions that are very close to the time limit may result in TLE in the system test. Please measure the execution time in your program to terminate the process, or have enough margin in the execution time.

### Input

Input is given from Standard Input in the following format:

N M
x_1 y_1
\vdots
x_M y_M

• N is an odd number between 31 and 61, representing the number of vertical and horizontal grid points on the grid paper.
• M denotes the number of initially placed dots, satisfying N\leq M\leq \lfloor N^2/12 \rfloor.
• (x_1, y_1), \cdots, (x_M, y_M) denote the coordinates of the M dots, each of which satisfies \lfloor N/4\rfloor\leq x_i,y_i\leq\lfloor 3N/4\rfloor.

### Output

Let K be the total number of operations and (x_{i,1}, y_{i,1}), (x_{i,2}, y_{i,2}), (x_{i,3}, y_{i,3}), (x_{i,4}, y_{i,4}) be the four points chosen in the i-th operation. Then, output to Standard Output in the following format.

K
x_{1,1} y_{1,1} x_{1,2} y_{1,2} x_{1,3} y_{1,3} x_{1,4} y_{1,4}
\vdots
x_{K,1} y_{K,1} x_{K,2} y_{K,2} x_{K,3} y_{K,3} x_{K,4} y_{K,4}


The order of the four points can be clockwise or counterclockwise, but (x_{i,1}, y_{i,1}) must be the point where the new dot is placed.

Show example

### Input Generation

The input of seed=0 is manually created and is not included in the provisional or system test. Let \mathrm{rand}(L,U) be a function that generates a uniform random integer between L and U, inclusive.

#### Generation of N and M

N=\mathrm{rand}(15, 30)\times 2 + 1, M=\mathrm{rand}(N, \lfloor N^2/12 \rfloor).

#### Generation of (x_i, y_i)

M grid points (x,y) satisfying \lfloor N/4\rfloor\leq x,y\leq\lfloor 3N/4\rfloor are chosen at random.

### Tools (Input generator and visualizer)

You are allowed to share output images (PNG) of the provided visualizer for seed=0 on twitter during the contest. Note that sharing in animation format is prohibited. You have to use the specified hashtag and public account. You can only share visualization results and scores for seed=0. Do not share GIFs, output itself, scores for other seeds or mention solutions or discussions.

List of shared images

### Sample Input 1

33 58
13 24
14 24
15 24
16 24
17 24
12 23
18 23
11 22
19 22
10 21
20 21
9 20
21 20
8 19
15 19
18 19
22 19
8 18
12 18
15 18
18 18
22 18
8 17
12 17
15 17
18 17
22 17
8 16
12 16
15 16
18 16
22 16
8 15
12 15
15 15
18 15
22 15
9 14
12 14
15 14
18 14
21 14
10 13
12 13
15 13
18 13
20 13
22 13
11 12
12 12
15 12
18 12
19 12
23 12
12 11
15 11
18 11
24 11


### Sample Output 1

20
9 15 12 12 15 15 12 18
15 20 12 17 15 14 18 17
23 22 19 22 19 12 23 12
23 14 22 15 21 14 22 13
10 14 10 13 12 13 12 14
11 11 12 11 12 12 11 12
18 20 15 20 15 19 18 19
19 16 22 19 21 20 18 17
12 19 12 18 15 18 15 19
15 22 12 19 15 16 18 19
14 22 15 22 15 24 14 24
15 8 18 11 15 14 12 11
10 15 9 15 9 14 10 14
11 18 12 19 10 21 9 20
22 23 20 21 21 20 23 22
21 15 18 15 18 14 21 14
15 26 13 24 15 22 17 24
20 20 16 24 14 22 18 18
21 17 18 20 15 17 18 14
11 14 10 13 11 12 12 13