题目大意:
给你一个圆和圆内到圆心距离相等的两点 P Q ,让你在圆上找到一个点 K ,使得这 PK + QK 最小。
分析:
学到一个几何方面的知识,这么好用的东西之前我居然没听说过,叫做反演。就是在OP的延长线上,取A,使得
未AC代码:
#include<bits/stdc++.h>
using namespace std;
double r,px,py,qx,qy,ax,ay,bx,by;
int test;
int main()
{
scanf("%d",&test);
while(test--)
{
scanf("%lf%lf%lf%lf%lf",&r,&px,&py,&qx,&qy);
double op,oq,pq;
op=sqrt(px*px+py*py);
oq=op;
pq=sqrt((px-qx)*(px-qx)+(py-qy)*(py-qy));
if(op+oq-pq<1e-9) { double ans=2.0*sqrt(op*op+r*r); printf("%.7f\n",ans); continue; } double oa=r*r/op; double c=(op*op+oq*oq-pq*pq)/(2.0*op*oq); double cc=sqrt((c+1)/2.0); //cout<<cc<<endl; /*if(cc<=1e-6) { double ans=oa/r/pq; //cout<<1; printf("%lf\n",ans); continue; }*/ double dis=oa*cc; if(dis>r)
{
double x=sqrt(op*op+r*r-cc*2.0*op*r);
double ans=2*x;
printf("%.7f\n",ans);
//cout<<"dsa";
}
else
{
double ans=pq*r/op;
printf("%.7f\n",ans);
}-
}
}
样例已过,精度或边界问题。