Fear of the Dark

jcs_pp · 2025-09-25 19:27:36 · 题解

时间复杂度： O(1) 可过。

分两种情况。

1

一个灯笼可以包括两个点。

2

要走两个灯笼。

这种方法要注意的是：

1. 两个点都要覆盖。
2. 两个圆要有交点。

代码注意细节，附有详细注释。

#include<bits/stdc++.h>
using namespace std;
int T,px,py,ax,ay,bx,by;
double ss(int px,int py,int nx,int ny){//用勾股定理求两点距离 
    int x=px-nx,y=py-ny;
    return sqrtl(x*x+y*y);
}
double solve1(int x,int y){//第一种情况 
    double s1=ss(x,y,px,py); 
    double s2=ss(x,y,0,0);
    return max(s1,s2);
}
double solve2(int ax,int ay,int bx,int by){//第二种情况 
    double s1=ss(ax,ay,0,0); 
    double s2=ss(bx,by,px,py);
    double s3=ss(ax,ay,bx,by)/double(2.0);//要让两个圆相交 
    return max(s1,max(s2,s3));
}
int main(){
    cin>>T;
    while(T--){
        cin>>px>>py>>ax>>ay>>bx>>by;
        //注意：无法确定两个灯笼的位置，所以两种情况要互换灯笼位置 
        double ans1=min(solve1(ax,ay),solve1(bx,by));
        double ans2=min(solve2(ax,ay,bx,by),solve2(bx,by,ax,ay));
        printf("%.10lf\n",min(ans1,ans2));
    }
    return 0;
}