← 返回题目列表

Codeforces · 575/E

E. 观众骚乱

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

现在是拉马卡纳足球场的骚乱时间!愤怒的球迷涌入球场,警方发现自己陷入了困境。该场可以表示为由 (0,0) 和 (105, 105) 中的两个对角顶点定义的坐标系中的正方形。该正方形的边也被认为是在场内,其他一切都在场外。

一开始,场上有N名球迷。对于每个风扇,我们都会得到他的速度、整数 vi 以及他的整数坐标 (xi, yi)。具有这些坐标的风扇可能会移动,一秒钟后他可能位于任意点 (xi + p, yi + q),其中 0 ≤ |p| + |q| ≤ 六。 p、q 均为整数。

超出代表场地的方块的点被排除,所有其他点在一秒后都有相同的概率成为该特定风扇的位置。

安德烈是一位年轻有为的警官,他派出一架飞行无人机从上方拍摄骚乱照片。无人机摄像头的工作原理如下:

1. 选择三个具有整数坐标的点,使得一秒后有机会出现风扇。它们不能共线,否则相机将无法工作。保证并非所有粉丝的初始位置都在同一条线上。
2. 相机聚焦这些点并创建一个穿过这三个点的圆。一秒后拍摄照片(初始状态后一秒)。
3. 拍照时(对焦后一秒)圆圈上或圆圈内的所有内容都将显示在照片上。

您的目标是选择这三个点,以使照片上看到的预期粉丝数量最大化。如果有更多这样的选择,请选择其中给出半径最大的圆的那三个点。如果还有更合适的选择,任何一个都会被接受。如果您的答案符合上述条件,并且您返回的圆的半径比最佳圆的半径小 0.01,则您的输出将被视为正确。

没有测试的最佳半径大于 1010。

输入

第一行包含场上球迷的数量 N。接下来的 N 行包含三个整数:xi ,yi ,vi 。它们是任务中考虑的一秒间隔开始时风扇 i 的 x 坐标、y 坐标和速度。

- 3 ≤ N ≤ 105
- 0 ≤ xi, yi ≤ 105
- 0 ≤ vi ≤ 1000
- 所有数字均为整数

输出

您需要输出相机需要选择的三个点。将它们打印成三行,每行包含 x 坐标,然后包含 y 坐标,并用一个空格分隔。点的顺序并不重要。

示例

输入 #1

3
1 1 1
1 1 1
1 2 1

输出 #1

2 2
2 1
1 0