题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6097
题意：有一个圆心在原点的圆，给定圆的半径，给定P、Q两点坐标（PO=QO，P、Q不在圆外），取圆上一点D，求PD+QD的最小值。
解法：圆的反演。
很不幸不总是中垂线上的点取到最小值，考虑点在圆上的极端情况。
做P点关于圆的反演点P',OPD与ODP'相似，相似比是|OP| : r。
Q点同理。
极小化PD+QD可以转化为极小化P'D+Q'D。
当P'Q'与圆有交点时，答案为两点距离，否则最优值在中垂线上取到。
时间复杂度 O(1)
也有代数做法，结论相同。
优秀的黄金分割三分应该也是可以卡过的。
分析可以看这个博客：http://blog.csdn.net/qq_34845082/article/details/77099332
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
struct FastIO
{
static const int S = 1310720;
int wpos;
char wbuf[S];
FastIO() : wpos(0) {}
inline int xchar()
{
static char buf[S];
static int len = 0, pos = 0;
if(pos == len)
pos = 0, len = fread(buf, 1, S, stdin);
if(pos == len)
exit(0);
return buf[pos ++];
}
inline unsigned long long xuint()
{
int c = xchar();
unsigned long long x = 0;
while(c <= 32)
c = xchar();
for(; '0' <= c && c <= '9'; c = xchar())
x = x * 10 + c - '0';
return x;
}
inline long long xint()
{
long long s = 1;
int c = xchar(), x = 0;
while(c <= 32)
c = xchar();
if(c == '-')
s = -1, c = xchar();
for(; '0' <= c && c <= '9'; c = xchar())
x = x * 10 + c - '0';
return x * s;
}
inline void xstring(char *s)
{
int c = xchar();
while(c <= 32)
c = xchar();
for(; c > 32; c = xchar())
* s++ = c;
*s = 0;
}
inline double xdouble()
{
bool sign = 0;
char ch = xchar();
double x = 0;
while(ch <= 32)
ch = xchar();
if(ch == '-')
sign = 1, ch = xchar();
for(; '0' <= ch && ch <= '9'; ch = xchar())
x = x * 10 + ch - '0';
if(ch == '.')
{
double tmp = 1;
ch = xchar();
for(; ch >= '0' && ch <= '9'; ch = xchar())
tmp /= 10.0, x += tmp * (ch - '0');
}
if(sign)
x = -x;
return x;
}
inline void wchar(int x)
{
if(wpos == S)
fwrite(wbuf, 1, S, stdout), wpos = 0;
wbuf[wpos ++] = x;
}
inline void wint(long long x)
{
if(x < 0)
wchar('-'), x = -x;
char s[24];
int n = 0;
while(x || !n)
s[n ++] = '0' + x % 10, x /= 10;
while(n--)
wchar(s[n]);
}
inline void wstring(const char *s)
{
while(*s)
wchar(*s++);
}
inline void wdouble(double x, int y = 8)
{
static long long mul[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000, 10000000000LL, 100000000000LL, 1000000000000LL, 10000000000000LL, 100000000000000LL, 1000000000000000LL, 10000000000000000LL, 100000000000000000LL};
if(x < -1e-12)
wchar('-'), x = -x;
x *= mul[y];
long long x1 = (long long) floorl(x);
if(x - floor(x) >= 0.5)
++x1;
long long x2 = x1 / mul[y], x3 = x1 - x2 * mul[y];
wint(x2);
if(y > 0)
{
wchar('.');
for(size_t i = 1; i < y && x3 * mul[i] < mul[y]; wchar('0'), ++i);
wint(x3);
}
}
~FastIO()
{
if(wpos)
fwrite(wbuf, 1, wpos, stdout), wpos = 0;
}
} io; const double eps = 1e-8;
double getDis(double x, double y){
return sqrt(x*x+y*y);
}
double r,x1,y1,x2,y2; int main()
{
int T = io.xint();
while(T--)
{
r = io.xdouble();
x1 = io.xdouble();
y1 = io.xdouble();
x2 = io.xdouble();
y2 = io.xdouble();
double d0 = getDis(x1, y1);
if(fabs(d0)<=eps){//p和q和原点重合
printf("%.8f\n", 2*r);
continue;
}
double k = r*r/d0/d0;//用这个比例确定p和q的反演点
double x3=x1*k, x4=x2*k;
double y3=y1*k, y4=y2*k;
double mx=(x3+x4)/2.0,my=(y3+y4)/2.0;
double ans;
double d = getDis(mx, my);
if(d <= r){//判断反演点和半径的关系 如果两个反演点的中点到圆心的距离小于半径
double dis = getDis(x3-x4,y3-y4);
ans = dis*d0/r;
}
else{//其他的即是连线与圆相离时的状态 这时候的d点是p和q的反演点的连线的中垂线与圆的交点
double kk=r/d;//其他的即是连线与圆相离时的状态 这时候的d点是p和q的反演点的连线的中垂线与圆的交点
double smx = mx*kk, smy = my*kk;
ans = 2*getDis(smx-x1,smy-y1);
}
printf("%.8f\n", ans);
}
return 0;
}