3677. 回收卫星

单点时限: 1.0 sec

内存限制: 256 MB

“这个世上没有无用的齿轮,也只有齿轮本身能决定自己的用途。”

就像太空中的卫星,虽然不计其数,但都各司其职。

但没有一个东西是能够永远无损的。为了便于回收及修理,卫星在故障后会生成一个球形的星场,与之配对的感应器能判断其是否在星场内。

QQ 小方现在要负责卫星的回收工作,他负责使用这些感应器锁定卫星的位置。QQ 小方有卫星基本的运动信息,因此每次工作时,他都能保证自己与卫星保持相对静止,以及自己在星场内。因此,可以将 QQ 小方看作空间直角坐标系的原点 $(0,0,0)$,而星场是一个中心坐标为 $(x,y,z)$ ($-10^9 \le x,y,z \le 10^9$) ,半径为 $r$ ($1 \le r \le 10^9$) 且包含原点的球,其中 $x,y,z,r$ 都是整数。但接下来,QQ 小方需要你的帮助。

为了回收卫星,QQ 小方每次能向一个整点发射一个感应器,感应器会返回它是否在星场里。由于经费紧张,QQ 小方只能发射不超过 $200$ 个感应器,你能帮助他找到卫星的具体坐标 $(x,y,z)$ 吗?

星场边界上的点视为在星场内部。

交互流程

每一行输出四个整数 $0,x_i,y_i,z_i$,代表向 ($x_i,y_i,z_i$) 发射一个感应器。随后,交互程序会输出 $1$ / $0$,代表感应器在 / 不在星场内。

收集足够多的数据之后,输出四个整数 $1,x,y,z$,代表确定卫星的坐标是 $(x,y,z)$。之后,你的程序不应再有任何输出。

样例

Input
0
0
0
0
0
0
Output
0 2 0 0
0 -2 0 0
0 0 2 0
0 0 -2 0
0 0 0 2
0 0 0 -2
1 0 0 0

提示

对于样例:

球场的中心是 ($0,0,0$),半径为 $1$。

在交互过程中,依次访问了 ($2,0,0$), ($-2,0,0$), ($0,2,0$), ($0,-2,0$), ($0,0,2$), ($0,0,-2$) 六个点,但这六个点都不在球场内。因为原点在球场内,所以球场中心一定位于 ($0,0,0$),半径为$1$。(当然,也有可能是运气好,但这个球的中心的确是($0,0,0$) 。)

85 人解决,105 人已尝试。

100 份提交通过,共有 544 份提交。

3.8 EMB 奖励。

创建: 1 年,8 月前.

修改: 1 年,8 月前.

最后提交: 2 月前.

来源: EOJ Monthly 2019.2

题目标签