迄今为止我认为写的最详细的一篇。
考虑二分。
思路
我们把两盏灯分别命名为 \(A\) 和 \(B\)。
如何走回家？
走回家有四种走法。
- 最开始在 \(A\) 所照的区域内，家也在 \(A\) 所照的区域内，这样就可以直接走到家。
- 最开始在 \(A\) 所照的区域内，家在 \(B\) 所照的区域内，先走到 \(B\) 所照的区域内，再走回家。
- 最开始在 \(B\) 所照的区域内，家也在 \(B\) 所照的区域内，这样也可以直接走到家。
- 最开始在 \(B\) 所照的区域内，家在 \(A\) 所照的区域内，先走到 \(A\) 所照的区域再回家。
这些走法是需要判断是否可行的，比如如果做开始不在 \(A\) 所照的区域内，那么第一种和第二种走法都不行。
怎样判断是否在此区域内或是否能走到另一个区域？
- 判断在不在区域内看圆心和当前点的距离是否小于圆的半径。
- 判断能不能走到另一个圆，即两个圆是否相切或相交，只需要判断两个圆心的距离是否小于它们的半径之和。
知道前面这些后，我们基本上就可已做出这题了。
可以采用二分答案，二分圆的半径，如果当前的半径符合要求，即可以回到家，则将当前半径是一个合法的答案，记录并缩小二分上界。否则增加二分下界。
符合要求的话，具体而言，就是看看能不能用上面四种走法回到家。
AC CODE
#include <bits/stdc++.h>
using namespace std;
double px,py,ax,ay,bx,by;
double diss(int x,int y,int x2,int y2){
return sqrt(1.0*(x-x2)*(x-x2)+1.0*(y-y2)*(y-y2));
}
inline bool check(double r){
if(diss(0,0,ax,ay)<=r){
if(diss(ax,ay,px,py)<=r)return true;
if(diss(ax,ay,bx,by)<=2*r){
if(diss(bx,by,px,py)<=r)return true;
}
}
if(diss(0,0,bx,by)<=r){
if(diss(bx,by,px,py)<=r)return true;
if(diss(ax,ay,bx,by)<=2*r){
if(diss(ax,ay,px,py)<=r)return true;
}
}
return false;
}
int main(){
int T;
cin>>T;
while(T--){
cin>>px>>py>>ax>>ay>>bx>>by;
double l=0,r=1e7,ans;
while(r-l>1e-10){
double mid=(l+r)/2;
if(check(mid)){
r=mid;
ans=mid;
}
else{
l=mid;
}
}
printf("%.10lf\n",ans);
}
return 0;
}