题目链接: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;
}

最新文章

  1. wpf的研究和反思
  2. node.js 包教不包会 (Windows版详解)
  3. Codeforces Round #250 (Div. 1) B. The Child and Zoo 并查集
  4. 学习记录:浏览器JAVASCRIPT里的WINDOWS,DOCUMNET
  5. Windows phone 之常用控件
  6. Map的内容按字母顺序排序
  7. Java HashSet和LinkedHashSet的用法
  8. ajaxFileUpload+struts2实现多文件上传(动态添加文件上传框)
  9. ecos的mvcl
  10. 2017-2018-2 PDE 讨论班
  11. 【开发】iOS入门 - UIViewController学习笔记
  12. Dockerfile文件制作自己的镜像
  13. AspNetPager 控件使用
  14. GNS3的使用2
  15. Java 多线程查找文件中的内容
  16. Binary file to C array(bin2c)
  17. [转]extern与头文件(*.h)的区别和联系
  18. NuGet服务器搭建教程
  19. JavaScript类库汇总
  20. javaweb(三十一)——国际化(i18n)

热门文章

  1. 【转】TCP拥塞控制,慢启动、拥塞避免、快重传以及快恢复
  2. MySQL基础原创笔记(一)
  3. CF724E Goods transportation
  4. 用camke编译python程序
  5. Educational Codeforces Round 61 (Rated for Div. 2) D,F题解
  6. mysql的主从复制原理与实现
  7. 三大linux系统对比
  8. bzoj 2124 等差子序列 树状数组维护hash+回文串
  9. gulp压缩css和js
  10. [技巧篇]07.JSON.parse() 和 JSON.stringify()