潘家园做网站公司,wordpress 不同站点,哪里有网站制作服务,可视化编辑 wordpress题干#xff1a;
单测试点时限: 1.0 秒
内存限制: 256 MB
“这个世上没有无用的齿轮#xff0c;也只有齿轮本身能决定自己的用途。”
就像太空中的卫星#xff0c;虽然不计其数#xff0c;但都各司其职。
但没有一个东西是能够永远无损的。为了便于回收及修理#xf…题干
单测试点时限: 1.0 秒
内存限制: 256 MB
“这个世上没有无用的齿轮也只有齿轮本身能决定自己的用途。”
就像太空中的卫星虽然不计其数但都各司其职。
但没有一个东西是能够永远无损的。为了便于回收及修理卫星在故障后会生成一个球形的星场与之配对的感应器能判断其是否在星场内。
QQ 小方现在要负责卫星的回收工作他负责使用这些感应器锁定卫星的位置。QQ 小方有卫星基本的运动信息因此每次工作时他都能保证自己与卫星保持相对静止以及自己在星场内。因此可以将 QQ 小方看作空间直角坐标系的原点 (0,0,0) 而星场是一个中心坐标为 (x,y,z) (−109≤x,y,z≤109 ) 半径为 r (1≤r≤109 ) 且包含原点的球其中 x,y,z,r 都是整数。但接下来QQ 小方需要你的帮助。
为了回收卫星QQ 小方每次能向一个整点发射一个感应器感应器会返回它是否在星场里。由于经费紧张QQ 小方只能发射不超过 200 个感应器你能帮助他找到卫星的具体坐标 (x,y,z) 吗
星场边界上的点视为在星场内部。
交互流程
每一行输出四个整数 0,xi,yi,zi 代表向 (xi,yi,zi ) 发射一个感应器。随后交互程序会输出 1 / 0 代表感应器在 / 不在星场内。
收集足够多的数据之后输出四个整数 1,x,y,z 代表确定卫星的坐标是 (x,y,z) 。之后你的程序不应再有任何输出。
样例
Input
0
0
0
0
0
0Output
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 ) 。
解题报告 因为题目中说了原点一定是其中的点所以我们直接分成三个坐标轴上也就是求x的时候其他两个坐标都是0分别二分求中点最后结果一定就是答案了。
以 x 轴为例因为原点在球内球面和 x 轴的正负半轴含原点一定各有一个交点。如果两个交点分别为 (x1,0,0 ) 和 (x2,0,0 )则球心一定在这两点所成线段的垂直平分面上。因为线段在 x 轴上所以所得到平面的表达式是 xx1x22 相当于确定了球心在 x 轴上的坐标。
因此只要求出两个交点的中点坐标即可。交点坐标可能含有小数但是依旧可以通过二分法求出半轴上第一个不在球内或最后一个在球内的点的坐标。对正负半轴各求一次根据对称性所得两点的中点坐标应该与真实交点中点坐标相同因此可以在约 2×3060 次操作内确定球心在 x 轴上的坐标。因为题干中说了最终答案为整数
同样地可以用此方法求出球心在 y 轴z 轴上的坐标得解。
有一个常见错误是二分交点从 109 开始。虽然 x,y,z,r≤109 但交点坐标绝对值可以大于 109 , 值 ≤2×109 。同时此时的 lr2 会在 lr 时爆 int。
还有就是注意交互题型如果要scanf读入的话一定不要忘了printf后面加fflush(stdout)。。
AC代码
#includebits/stdc.h
#define ll long long
using namespace std;
const ll INF2e9;
ll a[5];
void ask(int tp,int m) {for(int i1; i3; i)a[i]0;a[tp]m;printf(0 %lld %lld %lld\n,a[1],a[2],a[3]);fflush(stdout);
}
ll go(int tp) {ll l0,rINF,mid,ans10,ans20;int op;while(lr) {midl(r-l)/2;ask(tp,mid);scanf(%d,op);if(op)lmid 1,ans1 mid;else rmid - 1;}l-INF,r0;while(lr) {midl(r-l)/2;ask(tp,mid);scanf(%d,op);if(op)rmid-1,ans2 mid;else lmid1;}return (ans1ans2)/2;
}
int main()
{ll x,y,z;xgo(1);ygo(2);zgo(3);printf(1 %lld %lld %lld\n,x,y,z);return 0 ;
}
