题目链接：https://cn.vjudge.net/problem/HDU-6097
知识点： 计算几何、圆的反演
题目大意：
已知一个圆心在原点的圆的半径，再给定 \(P, Q\) 两点坐标（ \(PO=QO\)，\(P, Q\) 不在圆外），在圆上取一点 \(D\)，求 \(PD+QD\) 的最小值。
解题思路：
首先，\(P, Q\) 两点重合的情况要特判；
其次，\(P, Q\) 在圆上的情况也要特判（将 \(D\) 点放在 \(P\) 或 \(Q\) 点上即可，答案为 \(|PQ|\) ）；
最后一种情况：
先介绍一下圆的反演这个概念：
圆的反演就是对于圆\(O\)所在平面的任意一点 \(S\) ，找到一个点 \(S’\) ，使得满足以下条件：
\(1)\) \(S’\) 在直线 \(OS\) 上；
\(2)\) \(|OS||OS’| = R^2\)，\(R\) 为圆的半径（由这个条件可以利用相似三角形的性质推导出反演的一个性质：对于圆上任意一点 \(P\) ，有 \(\triangle POS \sim \triangle S’OP\)）；
圆的反演点还有一个重要的性质：圆内的反演点在圆外，圆外的反演点在圆内，圆上的反演点是它本身。
具体可以看看这篇文章。
先求出 \(P, Q\) 的反演点 \(P’, Q’\)，由反演的性质易知 \(\triangle P’OD \sim \triangle DOP\)，\(PD = PO*P’D/r\)，同理有 \(QD = QO*Q’D/r\)，则 \(PD+QD = PO/r(P’D+Q’D)\)。故我们只需求出 \(P’D+Q’D\) 的最小值即可，因为圆内的反演点在圆外，而圆外的情况是比较容易处理的。
如果 \(P’Q’\) 与圆有交点，则 \(P’D+Q’D\) 的最小值即为 \(|P’Q’|\)；否则 \(D\) 取 \(P’Q’\) 的中垂线与圆的交点。
具体细节请看代码。
AC代码：
#include <bits/stdc++.h>
using namespace std;
const double eps=1e-;
int dcmp(double x){
if(fabs(x)<eps) return ;
else return x<?-:;
}
struct Point{
double x,y;
Point(double x=,double y=):x(x),y(y){}
};typedef Point Vector;
Vector operator +(Vector A,Vector B){
return Vector(A.x+B.x,A.y+B.y);
}
Vector operator -(Point A,Point B){
return Vector(A.x-B.x,A.y-B.y);
}
Vector operator *(double p,Vector A){
return Vector(A.x*p,A.y*p);
}
double Dis(Point A,Point B){//求两点距离
return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}
double Dot(Vector A,Vector B){//求向量点积
return A.x*B.x+A.y*B.y;
}
double Length(Vector A){
return sqrt(Dot(A,A));
}
double Cross(Vector A,Vector B){
return A.x*B.y-A.y*B.x;
}
Point O;//坐标原点 Point Inver(Point a,double r){//求反演点
double dis=sqrt(a.x*a.x+a.y*a.y);
double t=r*r/dis/dis;
return Point(t*a.x,t*a.y);
}
double DistanceToLine(Point P,Point A,Point B){//求直线AB到点P的距离
Vector v1=B-A,v2=P-A;
return fabs(Cross(v1,v2))/Length(v1);
}
double cal(Point A,Point B,double r){//求直线AB的中垂线与圆的交点D，并返回|AD|+|BD|
double dis=Dis(A,O);
double ang=acos(Dot(A,B)/(dis*dis))/2.0;//利用cos<v1,v2> = v1*v2/(|v1||v2|)这条性质求两个向量的夹角的一半
return 2.0*sqrt(r*r+dis*dis-*r*dis*cos(ang));
} int main(){
// freopen("in.txt","r",stdin);
int T;
int r1,xq1,yq1,xp1,yp1;
Point P,Q,rP,rQ;
scanf("%d",&T);
while(T--){
scanf("%d",&r1);
scanf("%d%d%d%d",&xp1,&yp1,&xq1,&yq1);
P=Point((double)xp1,(double)yp1),Q=Point((double)xq1,(double)yq1);
double r=(double)r1;
if(xq1==xp1&&yq1==yp1){//特判1
printf("%.7lf\n",2.0*(r-Dis(P,O)));
continue;
}
if(xp1*xp1+yp1*yp1==r1*r1){//特判2
printf("%.7lf\n",Dis(P,Q));
continue;
}
rP=Inver(P,r),rQ=Inver(Q,r);
double d=DistanceToLine(O,rP,rQ); if(dcmp(d-r)>)
printf("%.7lf\n",cal(P,Q,r));
else
printf("%.7lf\n",Dis(P,O)/r*Dis(rP,rQ));
}
return ;
}
