← 返回题目列表

Codeforces · 1196/C

C. 机器人突围

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

$$$n$$$ 机器人逃离了你的实验室!你必须尽快找到它们,因为这些机器人是实验性的,它们的行为还没有经过测试,所以它们可能真的很危险!

幸运的是,即使你的机器人逃跑了,你仍然对它们有一定的控制权。首先,你知道每个机器人的位置:你生活的世界可以被建模为一个无限的坐标平面,第 $$$i$$$ 个机器人当前位于坐标为 ($$$x_i$$$, $$$y_i$$$) 的点。此外,您可以向所有机器人发送一个命令。该命令应包含两个整数$$$X$$$和$$$Y$$$,当每个机器人收到此命令时,它开始向坐标为($$$X$$$,$$$Y$$$)的点移动。机器人在两种情况下停止运动:

- 要么达到 ($$$X$$$, $$$Y$$$);
- 或者它不能更接近 ($$$X$$$, $$$Y$$$)。

正常情况下,所有机器人都应该能够从坐标平面的任意点到达任意其他点。每个机器人通常可以执行四个动作来移动。我们将机器人的当前坐标表示为 ($$$x_c$$$, $$$y_c$$$)。然后移动系统允许它移动到四个相邻点中的任意一个:

1. 第一个动作允许它从 ($$$x_c$$$, $$$y_c$$$) 移动到 ($$$x_c - 1$$$, $$$y_c$$$);
2. 第二个动作允许它从 ($$$x_c$$$, $$$y_c$$$) 移动到 ($$$x_c$$$, $$$y_c + 1$$$);
3. 第三个动作允许它从 ($$$x_c$$$, $$$y_c$$$) 移动到 ($$$x_c + 1$$$, $$$y_c$$$);
4. 第四个动作允许它从 ($$$x_c$$$, $$$y_c$$$) 移动到 ($$$x_c$$$, $$$y_c - 1$$$)。

不幸的是,一些机器人的某些运动系统似乎出现了故障。对于每个机器人,您都知道它可以执行哪些操作,不能执行哪些操作。

您想要发送命令,以便所有机器人聚集在同一点。为此,您必须选择一对整数 $$$X$$$ 和 $$$Y$$$,以便每个机器人都能到达该点 ($$$X$$$, $$$Y$$$)。能不能找到这样一个点呢?

输入

第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 10^5$$$) — 查询数。

然后是 $$$q$$$ 查询。每个查询都以包含一个整数的一行开头 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 查询中的机器人数量。接下来是 $$$n$$$ 行,这些行中的第 $$$i$$$ 描述了当前查询中的第 $$$i$$$ 机器人:它包含六个整数 $$$x_i$$$、$$$y_i$$$、$$$f_{i, 1}$$$、$$$f_{i, 2}$$$、$$$f_{i, 3}$$$ 和$$$f_{i, 4}$$$ ($$$-10^5 \le x_i, y_i \le 10^5$$$, $$$0 \le f_{i, j} \le 1$$$)。前两个数字描述第 $$$i$$$ 个机器人的初始位置,后面四个数字描述第 $$$i$$$ 个机器人可以使用哪些动作来移动(如果第 $$$i$$$ 个机器人可以使用第 $$$j$$$ 个动作,则 $$$f_{i, j} = 1$$$;如果不能使用第 $$$j$$$ 个动作,则 $$$f_{i, j} = 0$$$第 $$$j$$$ 个动作)。

保证所有查询的机器人总数不超过$$$10^5$$$。

输出

您应该按照这些查询在输入中出现的顺序独立回答每个查询。

要回答查询,您应该执行以下操作之一:

- 如果不可能找到所有$$$n$$$机器人都能到达的点,则在单独的一行上打印一个数字$$$0$$$;
- 如果可以找到所有 $$$n$$$ 机器人均可到达的点,请在同一行上打印三个空格分隔的整数:$$$1$$$ $$$X$$$ $$$Y$$$,其中 $$$X$$$ 和 $$$Y$$$ 是所有 $$$n$$$ 机器人可到达的点的坐标。 $$$X$$$ 和 $$$Y$$$ 的绝对值均不应超过 $$$10^5$$$;保证如果存在至少一个所有机器人均可到达的点,则至少其中一个点的坐标绝对值不超过$$$10^5$$$。

示例

输入 #1

4
2
-1 -2 0 0 0 0
-1 -2 0 0 0 0
3
1 5 1 1 1 1
2 5 0 1 0 1
3 5 1 0 0 0
2
1337 1337 0 1 1 1
1336 1337 1 1 0 1
1
3 5 1 1 1 1

输出 #1

1 -1 -2
1 2 5
0
1 -100000 -100000