The 2019 ACM-ICPC China Shannxi Provincial Programming Contest C.Angel's Journey

傷城~ 2022-04-25 06:36 160阅读 0赞

## 题意： ##

## T(T<=500)组样例，每组样例给出rx,ry,r,x,y(-100<=rx,ry,x,y<=100,0<r<=100) ##

## 代表被救的人在(rx,ry-r)位置，且(rx,ry)为圆心有一个半径为r的圆 ##

## 你从圆外(x,y)出发，题目保证y>ry， ##

## y=ry及这条水平线以下的圆外部分是海，圆内部也是海，都不能经过 ##

## 问(x,y)到(rx,ry-r)的最短距离 ##

## 分析：有关切线的问题一定要往三角形上面靠，这样就简单多了。 ##

## ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvZGU5MjAwNw_size_16_color_FFFFFF_t_70][]   记A(x,y)，O(rx,ry)，S(rx,ry-r)，D(rx+r,ry)，E(rx-r,ry) ##

## 过A的直线与圆的切点F，坐标未知 ##

## 考虑棕色边的三角形AOS，余弦定理求顶角AOS， ##

## 余弦定理求直角三角形AFO的角AOF，作差得角FOS ##

## ①角FOS小于90度，说明FOS在海里，不可通过直线达，取点E和点D的较近点，再走1/4弧 ##

## ②角FOS大于90度，FOS可以通过与切点的线段到达，再走圆上一段弧即可 ##

## 这种判断，省去了对两个切点的分别判断 ##

## 参考博客：[https://blog.csdn.net/code92007/article/details/90582566][https_blog.csdn.net_code92007_article_details_90582566] ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    const double pi=acos(-1);
    int t,rx,ry,r,x,y;
    
    int dis(int x,int y,int i,int j) {
        return (x-i)*(x-i)+(y-j)*(y-j);
    }
    
    int main() {
        while(~scanf("%d",&t)) {
            while(t--) {
                scanf("%d%d%d%d%d",&rx,&ry,&r,&x,&y);
                int d1=dis(rx,ry,x,y),d2=dis(rx,ry-r,x,y);
                double ag1=acos(1.0*(d1+r*r-d2)/(2.0*r*sqrt(d1)));
                double ag2=acos(1.0*r/sqrt(d1));
                double ag3=ag1-ag2;
                if(ag3<=pi/2) {
                    double s=pi/2*r;
                    if(x>rx) s+=sqrt(dis(x,y,rx+r,ry));
                    else s+=sqrt(dis(x,y,rx-r,ry));
                    printf("%.4f\n",s);
                }else {
                    printf("%.4f\n",ag3*r+sqrt(d1-r*r));
                }
            }
        }
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvZGU5MjAwNw_size_16_color_FFFFFF_t_70]: /images/20220126/5933aa9ea5374b1baafd83bae5d28841.png
[https_blog.csdn.net_code92007_article_details_90582566]: https://blog.csdn.net/code92007/article/details/90582566