Question

Monocarp 在一个二维平面上，他的初始点在 \(O=(0,0)\) ，他需要到 \(P(P_x,P_y)\)

不幸的是，他能走的范围在两个圆内，我们给出了两个圆的坐标 \(A=(A_x,A_y)\) ，\(B=(B_x,B_y)\) 两个圆的半径相同，我们需要找到最小的半径让 Monocarp 能同 \(O\) 走到 \(P\)

Solution

这题可以二分+check，但是好像会被卡精度

其实，这题分类讨论就好了

• 只经过一个圆

• 经过两个圆，需要两个圆相交

Code

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
    while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
int T;
double Px,Py,Ax,Ay,Bx,By;
bool check_C_P(double x,double y,double R,double Px,double Py){
    return (Px-x)*(Px-x)+(Py-y)*(Py-y)<R*R;
}
bool check_C_C(double Ax,double Ay,double Bx,double By,double R){
    return (Ax-Bx)*(Ax-Bx)+(Ay-By)*(Ay-By)<(R*2)*(R*2);
}
bool check(double R){
    if(check_C_P(Ax,Ay,R,0,0)&&check_C_P(Ax,Ay,R,Px,Py)) return 1;
    if(check_C_P(Bx,By,R,0,0)&&check_C_P(Bx,By,R,Px,Py)) return 1;
    if(check_C_C(Ax,Ay,Bx,By,R)){
        if(check_C_P(Ax,Ay,R,0,0)&&check_C_P(Bx,By,R,Px,Py)) return 1;
        if(check_C_P(Bx,By,R,0,0)&&check_C_P(Bx,Ay,R,Px,Py)) return 1;
    }
    return 0;
}
int main(){
    // freopen("B.in","r",stdin);
    // freopen("B.out","w",stdout);
    T=read();
    while(T--){
        Px=read(),Py=read(),Ax=read(),Ay=read(),Bx=read(),By=read();
        double L=0,R=5e3,ans=R,mid;
        while(abs(R-L)>1e-9){
            mid=(R+L)/2;
            if(check(mid)){
                ans=min(ans,mid);R=mid;
            }
            else L=mid;
        }
        printf("%.9lf\n",ans);
    }
    return 0;
}

Summary

1. 这题具体实现的时候可以使用结构体/类的思想，把一个圆想成一个类，判断的时候不用写两遍了