Mindis

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1263    Accepted Submission(s): 150
Special Judge

Problem Description
The center coordinate of the circle C is O, the coordinate of O is (0,0) , and the radius is r.
P and Q are two points not outside the circle, and PO = QO.
You need to find a point D on the circle, which makes PD+QD minimum.
Output minimum distance sum.
 

Input
The first line of the input gives the number of test cases T; T test cases follow.
Each case begins with one line with r : the radius of the circle C.
Next two line each line contains two integers x , y denotes the coordinate of P and Q.

Limits
T≤500000
−100≤x,y≤100
1≤r≤100
 

Output
For each case output one line denotes the answer.
The answer will be checked correct if its absolute or relative error doesn't exceed 10−6.
Formally, let your answer be a, and the jury's answer be b. Your answer is considered correct if |a−b|max(1,b)≤10−6.
 

Sample Input
4
4
4 0
0 4
4
0 3
3 0
4
0 2
2 0
4
0 1
1 0
 

Sample Output
5.6568543
5.6568543
5.8945030
6.7359174
 

Source
2017 Multi-University Training Contest - Team 6
 

Recommend
liuyiding   |   We have carefully selected several similar problems for you:  6107 6106 6105 6104 6103 

刚开始想到反演，但是想错了。我想的是把圆上一个点当作反演中心，然后取一个任意的反演半径，之后圆反演成直线，再把两个点反演，就变成了“将军饮马”问题，但是敲出来并不正确。后来想了一下，反演后直线和圆的密度不一样，做完对称并不能连直线，所以结果才不对的吧。
最后做法是，圆心为反演中心，反演半径r²，反演圆和点，圆没变，点在圆外，去判断是否和反演圆有交点，没交点就是中垂线的那个距离，有交点就是随便取一个点，那个点反演回去（因为在圆上，其实还是那个点），再求距离，注意特判p,q重合。
AC代码
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>


using namespace std;


const double eps=1e-7;


int n,t;
double r,ans,p,q,ix;
double k;


struct point{
    double x, y;
    double len(){
        return sqrt(x * x + y * y);
    }
};


point fun(point a, point b, double k){
    point res, tmp;
    double len, tlen, blen;
    tmp.x = b.x - a.x;
    tmp.y = b.y - a.y;
    tlen = tmp.len();
    len = k / tlen;
    blen = b.len();
    res.x = tmp.x / tlen * len;
    res.y = tmp.y / tlen * len;
    res.x += a.x;
    res.y += a.y;
    return res;
}
double dis(point a,point b)
{
    return sqrt((b.y-a.y)(b.y-a.y) + (b.x-a.x)(b.x-a.x));
}


double sq(double x)
{
    return x*x;
}


point a,b,ia,ib,ta,o,tans,pans;


int main()
{
    //freopen("1002.in","r",stdin);
    //freopen("1002.out","w",stdout);
    scanf("%d",&t);
    o.x=o.y=0;
    while(t–)
    {
        scanf("%lf%lf%lf%lf%lf",&r,&a.x,&a.y,&b.x,&b.y);
        k=rr;
        ia=fun(o,a,k);
        ib=fun(o,b,k);
        if(a.x==b.x && a.y==b.y)
        {
            ans=2(r-dis(o,a));
        }
        else if(ia.x==ib.x)
        {
            if(abs(ia.x)>=r)
            {
                point tmp;
                if(ia.x>=0) tmp.x=r,tmp.y=0;
                else tmp.x=-r,tmp.y=0;
                ans=2dis(a,tmp);
                //cout<<111<<"&&&"<<endl;
            }
            else
            {
                double ty=sqrt(rr-ia.xia.x);
                point tmp;
                tmp.x=ia.x,tmp.y=ty;
                ans=dis(a,tmp)+dis(b,tmp);
                //cout<<222<<"&&&"<<endl;
            }
        }
        else
        {
            p=(ib.y-ia.y)/(ib.x-ia.x);
            q=ia.y-pia.x;
            double dieta=4ppqq-4*(pp+1)(qq-rr);
            if(dieta>=0)
            {
                point tmp;
                tmp.x=((-2pq)+sqrt(dieta))/(2*(pp+1));
                tmp.y=ptmp.x+q;
                ans=dis(a,tmp)+dis(b,tmp);
                //cout<<333<<"&&&"<<endl;
            }
            else
            {
                point tmp;
                tmp.x=(a.x+b.x)/2;
                tmp.y=(a.y+b.y)/2;
                double d=r-dis(tmp,o);
                double dx=dis(a,b)/2;
                ans=sqrt(dd+dxdx)*2;
                //cout<<444<<"&&&"<<endl;
            }
        }
        printf("%.7f\n",ans);
    }
    return 0;
}