HDU 6097Mindis(利用椭圆二分)

Mindis

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1887    Accepted Submission(s): 321
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

 

题意：在圆内有两点P,Q，圆心为O，PO=QO，给你圆的半径r和P,Q的坐标，求圆上一点到P,Q，两点距离最小值

思路：若以P,Q为焦点做一椭圆若椭圆与圆相交，那么交点处到P,Q的距离即为椭圆方程的2a，我们利用椭圆上任意一点到焦点的距离都为2a这一性质去找最小2a就为答案。

圆与椭圆相交的极限情况为椭圆与圆内切，此时的2a就是答案

对于所给的P,Q两点我们可以旋转坐标轴使得PQ直线与x轴平行，因为圆的圆心固定所以旋转并不会影响答案。

然后我们以P,Q为焦点做椭圆方程 ，h为PQ直线到原点距离

联立两个方程化简得

设

当时方程有解但是这个解可能为增根

利用求根公式求得

,

因为y1,y2的有效范围为[-r,r]所以还要判断一下有几个符合的实根

然后我们只用用二分来枚举b，然后判断有几个根就行

一：二：

三：四：

当y有两个不同的根时实际上b是大了所以符合的b其实在l到mid这一段区间(图一)，当y没有根时b应该在mid到r这段区间内(图二)，当y为有一个根时跳出即可(图三)，而二分的右边界r应该是椭圆与圆的上顶点相切这种情况(图四)，明显的此时b=r-h

故二分的范围为0~r-h

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const double eps=1e-10;
double r,c,h;
struct point
{
    double x,y;
}p,q;
double dis(point a,point b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int judge(double b)
{
    double a=sqrt(b*b+c*c);
    double A=a*a-b*b;
    double B=-2*h*a*a;
    double C=a*a*h*h+b*b*r*r-a*a*b*b;
    double delta=B*B-4*A*C;
    int num=0;
    if(delta>=0)
        {
            double y1=(-B+sqrt(delta))/(2*A);
            double y2=(-B-sqrt(delta))/(2*A);
            if(y1<=r&&y1>=-r)
                num++;
            if(y2<=r&&y2>=-r)
                num++;
        }
        return num;
}
double binarysearch(double l,double r)
{
    double mid;
    while(l+eps<r)
    {
        mid=(l+r)/2;
        int flag=judge(mid);
        if(flag>1)
            r=mid;
        else
            l=mid;
        if(flag==1)
            break;
    }
    return mid;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lf%lf%lf%lf%lf",&r,&p.x,&p.y,&q.x,&q.y);
        c=dis(p,q)/2;
        h=sqrt(p.x*p.x+p.y*p.y-c*c);
        double b=binarysearch(0,r-h);
        double a=sqrt(b*b+c*c);
        printf("%.7lf\n",2*a);
    }
    return 0;
}