深圳集团网站开发公司友情链接交换标准

给定两个点，原点和p点，现在需要从原点走到p点，有两个光源，a点和b点，这两个光源的半径相等，我们需要输出最小的半径的数值

代码

#include<bits/stdc++.h>
using namespace std;double dist(double x1,double y1,double x2,double y2)
{return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}int main()
{int t;scanf("%d",&t);while(t--){double px,py,ax,ay,bx,by;cin>>px>>py>>ax>>ay>>bx>>by;double oa=dist(0,0,ax,ay),ob=dist(0,0,bx,by);double pa=dist(px,py,ax,ay),pb=dist(px,py,bx,by);double r0=dist(ax,ay,bx,by)/2;double ans=1e9;ans=min(ans,max(oa,pa));ans=min(ans,max(ob,pb));ans=min(ans,max({r0,oa,pb}));ans=min(ans,max({r0,ob,pa}));printf("%.10lf\n",ans);}return 0;
}

赛时没有想清楚

标签是二分查找，几何，数学

//二分查找就是说分两种情况来进行讨论（估计不是这样子理解的...）

第一种情况是，o,p两个点都在同一个圆内，假设o,p这两个点都在a为圆心的圆内，需要覆盖o到p的路径，取oa,pa的最大值，才可以满足条件，同时在b圆里面也是同理，得到的这两个最大值取一个最小值，因为这两个最大值的较大者表示的是放弃比较近的圆，选择另一个比较远的圆，明显不符合条件，所以需要取两个最大值的较小者

第二种情况是，o,p两个点不在同一个圆，有两种情况，相切或者相交，考虑o在a圆内，p在b圆内，只要oa，pb可以覆盖就可以，但是还需要考虑一个条件，覆盖之后能不能相交或者相切，相交或者相切的条件是半径大于等于ab/2（也就是相切时候的半径），第二个样例表示的是两个圆相切，r0(相切时候半径)>oa的情况，假设oa>r0(相切时候半径)，表示的就是相交的情况，需要覆盖整个路径的话就取r0,oa,pb的最大值，o在b圆内，p在a圆内也是一样的道理

最后面为什么要取最小值呢，弄不太懂（为什么取上述所有情况的最小值）

考虑到我们的每一种情况取到的都是当前情况的最优解了，也就是说对于特定的样例，比如说o,p都在a圆内，取oa,pa的最大值就是答案需要的半径，这个答案需要的半径一定比oa,pb,r0这三个元素的最大值要小，（很明显pb或者r0是最大的），但是oa,pa的最大值比pb(或者r0)要小

#include<bits/stdc++.h>
using namespace std;double dist(double x1,double y1,double x2,double y2)
{return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}int main()
{int t;scanf("%d",&t);while(t--){double px,py,ax,ay,bx,by;cin>>px>>py>>ax>>ay>>bx>>by;double oa=dist(0,0,ax,ay),ob=dist(0,0,bx,by);double pa=dist(px,py,ax,ay),pb=dist(px,py,bx,by);double r0=dist(ax,ay,bx,by)/2;double ans=max(oa,pa);ans=min(ans,max(ob,pb));ans=min(ans,max({r0,oa,pb}));ans=min(ans,max({r0,ob,pa}));printf("%.10lf\n",ans);}return 0;
}