一个 $k \approx 2n+12$ 的构造

构造

证明

设身体循环 $r_1$ 次，尾巴循环 $r_2$ 次，则

$$n=4r_1+14+r_2$$ $$k=8r_1+38+3r_2$$

令

$$(n-14)\div4=r_1 \cdots r_2$$

即可， 此时有

$$k=8\left\lfloor\frac{n-14}{4}\right\rfloor+3((n-14) ~\mathrm{mod}~ 4)+38 $$

则

$$2n+10\le k\le 2n+14$$

AC Code

标程都能下载了我在这放代码也行吧……

代码看着长其实很短，我写了一堆debug+封装+拆行，不长才怪。

#include <bits/stdc++.h>
using namespace std;

int n;

void small_main(){
    printf("%d\n", 3*n+4);
    printf(
        "%d %d\n%d %d\n%d %d\n%d %d\n",
        1, 1,
        1, 2,
        2, 1,
        2, 2
    );
    for (int i=1; i<=n; i++){
        printf(
            "%d %d\n%d %d\n%d %d\n",
            i+1, i+2,
            i+2, i+1,
            i+2, i+2
        );
    }
}

struct coord {
    int x, y;
};

const int maxdebug=80;
char buf[90][90];  // debug only

struct Canvas {
    vector<coord> ans;
    int cur_row = 1;

    void debug(){
        memset(buf, ' ', sizeof buf);
        for (int i=0; i<=maxdebug; i++){
            buf[i][maxdebug+2] = '\n';
            buf[i][maxdebug+3] = '\0';
        }
        for (coord &c: ans) {
            buf[c.x][c.y] = '#';
        }
        for (int i=0; i<=maxdebug; i++){
            cout << buf[i];
        }
    }

    void output(){
        printf("%d\n", ans.size());
        for (coord &c: ans) {
            printf("%d %d\n", c.x, c.y);
        }
    }
} canvas;

struct pattern {
    int offset;  // 左上角的 col-row
    vector<string> pat;

    void print(Canvas &out){
        bool jumped = false;

        int row = out.cur_row,
            col = out.cur_row + offset;
        for (int i=0; i<pat.size(); i++){
            string &s = pat[i];
            for (int j=0; j<s.size(); j++){
                if (s[j]!=' '){
                   out.ans.push_back({i+row, j+col});
                }
                if (s[j]=='*'){
                    out.cur_row += i;
                    jumped = true;
                }
            }
        }

        if (!jumped) {
            out.cur_row += pat.size();
        }
    }
};

// " ": 空白 
// ".": 四度点
// "#": 二度点
// "*": 连接标识点

pattern head = {
    0,
    {
        "   ##",
        " ##..#",
        " # #..#",
        "#.# #..#",
    }
};

pattern body = {
    -4,
    {
        "#..# #..#",
    }
};

pattern back = {
    -4,
    {
        "#..# #.#",
        " #..# #",
        "  #..#*",
        "   ##"
    }
};

pattern tail = {
    0,
    {
        " #",
        "#*",
    }
};

int main(){
    freopen("picture.in", "r", stdin);
    freopen("picture.out", "w", stdout);

    cin >> n;

    if (n<=20){
        small_main();
        return 0;
    }

    int round = (n - 14) / 4, 
        left  = (n - 14) % 4;

    head.print(canvas);
    while (round--) body.print(canvas);
    back.print(canvas);
    while (left--) tail.print(canvas);

    // canvas.debug();
    canvas.output();

    return 0;
}