#P4751. 邋遢大王
邋遢大王
题目描述
有一个 行 列的点阵,其中第 行第 列的点坐标为 。请画一条有方向的连续折线,经过点阵中的每个点至少一次。折线的每一段都至少经过两个点阵中的点。
求最少使用多少段有向线段,并给出一种达到这个数量的画法。折线可以从任意位置开始。段与段必须首尾相接,拐点可以在点阵外,也可以在点阵中两个给定点之间。输出的只是每段最先、最后经过的点阵中的点,因此相邻两段报告的点可以不同。
输入格式
第一行包含一个正整数 ,表示测试组数。接下来 行,每行包含两个正整数 。
每行相邻的整数之间恰好有一个空格,没有额外的空格。
输出格式
对每组数据输出 行。
第一行包含一个正整数 ,表示所需的最少段数。接下来按折线行进顺序输出 行,第 行包含四个正整数 。点 是该段最先经过的点阵中的点,点 是最后一个。两个点必须不同,坐标都要在点阵范围内。
若第 段与第 段的拐点恰好是点阵中的一个点,则 。若有多种最优方案,可以输出任意一种。每行相邻的整数之间恰好用一个空格分隔,没有额外的空格。
样例 #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

数据范围
,,。最多有 组数据满足 或 。