「PMOI-5」棋盘

Luogu

IDLGP8154

Time1000ms

Memory256MB

DifficultyP5

计算几何Special Judge枚举构造

给定一个无限大的棋盘（可以看做平面直角坐标系）和黑白子各 $n$ 颗，要求将黑白子不重叠地摆在棋盘的整点上，使得**恰好**存在 $n$ 条直线使得： - 其穿过且**仅**穿过黑白子**共** 4 颗。 - 其按顺序穿过黑，白，白，黑子。给出任意一种方案即可。 ## Input 输入数据仅一行，为题目中所述的 $n$。 ## Output 如果无法构造出方案，则输出 `NO`。否则输出 $2n+1$ 行：第一行输出 `YES`。第 $2\sim n+1$ 行每行两个整数，为白子坐标 $x_i,y_i$。第 $n+2\sim 2n+1$ 行每行两个整数，为黑子坐标 $x_j,y_j$。你需要保证 $-5\times 10^5\le x_i,y_i,x_j,y_j\le 5\times 10^5$。 [samples] ## Note 【样例解释】样例 2 解释：（输出按顺序为点 $A\sim N$（点 $A\sim G$ 为白子，点 $H\sim N$ 为黑子），直线如图所示）。 ![](https://cdn.luogu.com.cn/upload/image_hosting/zyo823p8.png) 【数据范围】 **本题采用捆绑测试。** - Subtask 1（10 pts）：$n\equiv 0 \pmod{7}$； - Subtask 2（20 pts）：$40\le n\le 400$； - Subtask 3（30 pts）：$1\le n\le 9$； - Subtask 4（40 pts）：无特殊限制。对于 $100\%$ 的数据，$1\le n\le 10^3$。 [SPJ地址](https://www.luogu.com.cn/paste/eamtmrw5) 使用方法：编译为 `checker.exe` 后命令行同一目录下输入 ```checker.exe chessboard.in chessboard.out chessboard.ans``` 需要搭配 `testlib.h` 一起使用，[testlib下载地址](https://github.com/MikeMirzayanov/testlib)。如果发现 SPJ 出锅了请找出题人。

Samples

Input #1

Output #1

NO

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "「PMOI-5」棋盘",
    "description": {
      "content": "给定一个无限大的棋盘（可以看做平面直角坐标系）和黑白子各 $n$ 颗，要求将黑白子不重叠地摆在棋盘的整点上，使得**恰好**存在 $n$ 条直线使得： - 其穿过且**仅**穿过黑白子**共** 4 颗。 - 其按顺序穿过黑，白，白，黑子。 给出任意一种方案即可。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8154"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一个无限大的棋盘（可以看做平面直角坐标系）和黑白子各 $n$ 颗，要求将黑白子不重叠地摆在棋盘的整点上，使得**恰好**存在 $n$ 条直线使得：\n\n- 其穿过且**仅**穿过黑白子**共** 4 颗。\n\n- 其按顺序穿过黑，白，白，黑子。\n\n给出任意一种方案即可。\n\n## Input\n\n输入数据仅一行，为题目中所述的 $n$。\n\n## Output\n\n如果无法构造出方案，则输出 `NO`。\n...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments