hdu6097 Mindis【圆的反演】

Tempo lv.1

发布时间：2022-11-28 12:13:35 196

相关标签： # php# c++

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6097

题意：有一个半径为R的圆，圆心在原点，圆里面存在两点P,Q，且PO=QO，现让你在圆上找一个点D，使得PD+QD的值最小，并输出这个值

解析：比赛的时候，三分不够优秀，过不去，赛后看了题解，然后学习了一下圆的反演，发现了一个新的大陆，通过圆的反演，就会发现，这个问题的求解就分成了两种情况，反演后结果如下

由上图可知，求PD+DQ的最小值就相当于求P^’D+Q^’D的最小值

①当P^’Q^’与圆有交点时，最小值肯定是P^’Q^’的长

②没有交点，那么D点应该位于圆心和P^’Q^’的中点的连线与圆的交点

#include <bits/stdc++.h>
using namespace std;
struct point
{
    double x,y;
    point() {}
    point (double x1,double y1)
    {
        x = x1;
        y = y1;
    }
};
double dis(point p1,point p2)
{
    return sqrt(1.0*(p1.x-p2.x)*(p1.x-p2.x)+1.0*(p1.y-p2.y)*(p1.y-p2.y));
}
double x_mul(point p0,point p1,point p2)
{
    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
int main(void)
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        double r;
        point p,q;
        scanf("%lf %lf %lf %lf %lf",&r,&p.x,&p.y,&q.x,&q.y);
        double op = dis(p,point(0,0));
        if(p.x==q.x && p.y==q.y)
        {
            printf("%.7f\n",2.0*(r-op));
            continue;
        }
        double tmp = 1.0*r*r/op/op;
        point p1,q1;
        p1.x = p.x*tmp;p1.y = p.y*tmp;
        q1.x = q.x*tmp;q1.y = q.y*tmp;
        double s = fabs(x_mul(point(0,0),p1,q1));
        double p1q1 = dis(p1,q1);
        double d = s/p1q1,ans;
        ans = p1q1;
        if(d>r)
        {
            d -= r;
            ans = 2*sqrt((p1q1/2.0)*(p1q1/2.0)+d*d);
        }
        ans = ans*op/r;
        printf("%.7f\n",ans);
    }
    return 0;
}

文章来源： https://blog.51cto.com/u_11435021/5880214

特别声明：以上内容（图片及文字）均为互联网收集或者用户上传发布，本站仅提供信息存储服务！如有侵权或有涉及法律问题请联系我们。