2019-icpc西安邀请赛-C
Angel’s Journey
“Miyane!” This day Hana asks Miyako for help again. Hana plays the part of angel on the stage show of the cultural festival, and she is going to look for her human friend, Hinata. So she must find the shortest path to Hinata’s house. The area where angels live is a circle, and Hana lives at the bottom of this circle. That means if the coordinates of circle’s center is ( r x , r y ) and its radius is r , Hana will live at ( r x , r y − r ) . Apparently, there are many difficulties in this journey. The area which is located both outside the circle and below the line y = r y is the sea, so Hana cannot pass this area. And the area inside the circle is the holy land of angels, Hana cannot pass this area neither. However, Miyako cannot calculate the length of the shortest path either. For the loveliest Hana in the world, please help her solve this problem! Input Each test file contains several test cases. In each test file: The first line contains a single integer T ( 1 ≤ T ≤ 500 ) which is the number of test cases. Each test case contains only one line with five integers: the coordinates of center r x 、 r y , the radius r , thecoordinates of Hinata’s house x 、 y . The test data guarantees that y > r y and ( x , y ) is out of the circle. ( − 10 2 ≤ r x , r y , x , y ≤ 10 2 , 0 < r ≤ 10 2 ) . Output For each test case, you should print one line with your answer (please keep 4 decimal places).
Sample Input
2
1 1 1 2 2
1 1 1 1 3
Sample Output
2.5708
3.8264
题意:
给定一个圆,不能走圆里面和圆下半部分,从圆的最低点到给定点,求最短距离。
利用极坐标系,先在圆弧上走,走到切点以后,走两点间最短路。
#include<bits/stdc++.h>
#define PI acos(-1)
using namespace std;
int main(){
int T;
scanf("%d",&T);
while(T--){
int X,Y,r,x,y;
scanf("%d %d %d %d %d",&X,&Y,&r,&x,&y);
double ans=0;
if(x>=X+r||x<=X-r){
ans+=2*r*PI/4;
ans+=sqrt((y-Y)*(y-Y)+min((x-(X+r))*(X-(X+r)),(x-(X-r))*(x-(X-r))));
}else{
double d=sqrt((y-Y)*(y-Y)+(x-X)*(x-X));
double A=abs(X-x)/d;
double a=r/d;
if(X==x){
ans+=0.5*PI-acos(r/d);
}else{
ans+=acos(A)-acos(a);
}
ans+=0.5*PI;
ans*=r;
ans+=sqrt(d*d-r*r);
}
printf("%.4lf\n",ans);
}
return 0;
}