← 返回题目列表

Codeforces · 1444/D

D. 矩形折线

中文机器翻译题面 查看原题

在平面上绘制一条闭合多段线,该多段线仅由垂直和水平线段(平行于坐标轴)组成。这些片段在水平和垂直片段之间交替(水平片段后面总是跟着垂直片段,反之亦然)。折线不包含严格的自相交,这意味着如果任何两个线段共享一个公共点,则该点是它们两个的端点(请参阅注释部分中的示例)。

不幸的是,折线被删除了,您只知道水平和垂直线段的长度。请构造与此类线段的描述相匹配的任何多段线,或者确定它不存在。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 200$$$)——测试用例的数量。

每个测试用例的第一行包含一个整数 $$$h$$$ ($$$1 \leq h \leq 1000$$$) — 水平线段的数量。以下行包含 $$$h$$$ 整数 $$$l_1, l_2, \dots, l_h$$$ ($$$1 \leq l_i \leq 1000$$$) - 折线水平线段的长度,顺序任意。

以下行包含一个整数 $$$v$$$ ($$$1 \leq v \leq 1000$$$) — 垂直线段的数量,后面跟着一行包含 $$$v$$$ 整数 $$$p_1, p_2, \dots, p_v$$$ ($$$1 \leq p_i \leq 1000$$$) — 长度折线的垂直线段,按任意顺序。

测试用例以空行分隔,所有测试用例的值 $$$h + v$$$ 之和不超过 $$$1000$$$。

输出

对于每个测试用例,如果存在至少一条满足要求的折线,则输出“是”,否则输出“否”。如果确实存在,则在接下来的 $$$n$$$ 行中按照折线遍历的顺序打印折线顶点的坐标:第 $$$i$$$ 行应包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ — 第 $$$i$$$ 顶点的坐标。

请注意,每个折线段必须是水平或垂直的,并且这些段应在水平和垂直之间交替。坐标的绝对值不应超过 $$$10^9$$$。

示例

输入 #1

2
2
1 1
2
1 1

2
1 2
2
3 3

输出 #1

Yes
1 0
1 1
0 1
0 0
No

输入 #2

2
4
1 1 1 1
4
1 1 1 1

3
2 1 1
3
2 1 1

输出 #2

Yes
1 0
1 1
2 1
2 2
1 2
1 1
0 1
0 0
Yes
0 -2
2 -2
2 -1
1 -1
1 0
0 0

输入 #3

2
4
1 4 1 2
4
3 4 5 12

4
1 2 3 6
2
1 3

输出 #3

Yes
2 0
2 3
3 3
3 7
4 7
4 12
0 12
0 0
No

注意

在第一个示例的第一个测试用例中,答案是“是”——例如,下图展示了一个满足要求的正方形:

在第二个示例的第一个测试用例中,也存在所需的折线。请注意,折线包含自相交,但仅在端点处:

在第二个示例的第二个测试用例中,所需的折线可能如下所示:

请注意,以下多段线不是有效的多段线,因为它包含的自交点不是某些线段的端点: