#P4751. 邋遢大王

    ID: 3871 传统题 1000ms 128MiB 尝试: 50 已通过: 20 难度: 7 上传者: 标签>难度分类提高+/省选-构造与建模递归构造对称性分析CF2300鸣谢Tangjz提供试题

邋遢大王

题目描述

有一个 nn 行 mm 列的点阵,其中第 ii 行第 jj 列的点坐标为 (i,j)(i,j)。请画一条有方向的连续折线,经过点阵中的每个点至少一次。折线的每一段都至少经过两个点阵中的点。

求最少使用多少段有向线段,并给出一种达到这个数量的画法。折线可以从任意位置开始。段与段必须首尾相接,拐点可以在点阵外,也可以在点阵中两个给定点之间。输出的只是每段最先、最后经过的点阵中的点,因此相邻两段报告的点可以不同。

输入格式

第一行包含一个正整数 TT,表示测试组数。接下来 TT 行,每行包含两个正整数 n,mn,m。

每行相邻的整数之间恰好有一个空格,没有额外的空格。

输出格式

对每组数据输出 l+1l+1 行。

第一行包含一个正整数 ll,表示所需的最少段数。接下来按折线行进顺序输出 ll 行,第 ii 行包含四个正整数 axi,ayi,bxi,byia_{x_i},a_{y_i},b_{x_i},b_{y_i}。点 ai=(axi,ayi)a_i=(a_{x_i},a_{y_i}) 是该段最先经过的点阵中的点,点 bi=(bxi,byi)b_i=(b_{x_i},b_{y_i}) 是最后一个。两个点必须不同,坐标都要在点阵范围内。

若第 ii 段与第 i+1i+1 段的拐点恰好是点阵中的一个点,则 bi=ai+1b_i=a_{i+1}。若有多种最优方案,可以输出任意一种。每行相邻的整数之间恰好用一个空格分隔,没有额外的空格。

样例 #1

样例输入 #1

3
1 2
2 3
3 3

样例输出 #1

1
1 2 1 1
3
2 3 1 2
1 1 2 1
2 2 1 3
4
1 1 3 3
3 3 3 1
2 1 1 2
1 3 2 3

样例的三组折线路线

数据范围

1≤T≤1001\le T\le100,1≤n,m≤10001\le n,m\le1000,nm>1nm>1。最多有 1010 组数据满足 n>10n>10 或 m>10m>10。