← 返回题目列表

Codeforces · 666/D

D. 连锁反应

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

与您有密切业务关系的 Berland 科学家小组在和平核能领域进行研究。特别是,他们发现将四个纳米机器人放在一块板的表面上,可以在某些条件下发生强大的链式反应。

准确地说,研究人员在平板上引入了直角笛卡尔坐标系,并选择了四个具有整数坐标的不同点,机器人最初将放置在这些点上。接下来,每个机器人将被分配与坐标轴平行的四个方向(上、下、左或右)之一。之后,每个机器人沿其方向移动整数距离(不同机器人的距离可能不同)。如果机器人位于面积为正且边平行于坐标轴的正方形的角上,链式反应就会开始。正方形的每个角都必须包含一个纳米机器人。如果机器人移动的时间更少,这种反应就会更强烈。我们可以假设机器人以单位速度移动。换句话说,机器人的最大移动距离越小,反应越强。

科学家们准备了一组盘子,并为每个盘子选择了机器人的起始位置。现在,他们要求您指定每个机器人在着陆后移动的方向,以使机器人行驶的最大长度尽可能小。

输入

第一行包含一个整数 t (1 ≤ t ≤ 50) — 车牌数量。

板的描述如下。每个板的描述由四行组成。每行由一对整数 xi, yi (- 108 ≤ xi, yi ≤ 108) 组成 - 下一个机器人的坐标。所有机器人都位于不同的位置。

注意,虽然问题可以在一个测试中包含多个记录,但您只能通过一个板块的测试来破解其他人的提交,即破解测试中的参数 t 应等于 1。

输出

单独打印所有板的答案。首先在单独的行中输入一个整数。如果科学家犯了一个不幸的错误,并且纳米机器人无法形成所需的正方形,请打印 -1。否则,打印最长机器人路径的最小可能长度。

如果存在解决方案,则在接下来的四行中打印两个整数 - 每个机器人移动后的位置。按照输入数据中指定的顺序打印机器人的位置。

如果有多个解决方案,您可以打印其中任何一个。

示例

输入 #1

2
1 1
1 -1
-1 1
-1 -1
1 1
2 2
4 4
6 6

输出 #1

0
1 1
1 -1
-1 1
-1 -1
-1