German Collegiate Programming Contest 2018 B. Battle Royale

Battle Royale games are the current trend in video games and Gamers Concealed Punching Circles (GCPC) is the most popular game of them all. The game takes place in an area that, for the sake of simplicity, can be thought of as a two-dimensional plane. Movement and positioning are a substantial part of the gameplay, but getting to a desired location can be dangerous. You are confident in your ability to handle the other players, however, while you are walking to your destination, there are two hazards posed by the game itself:

The game zone is bounded by a blue circle. Outside of this circle, there is a deadly force field that would instantly take you out of the game.
Inside the game zone, there is a red circle where you are exposed to artillery strikes. This circle is also too risky to enter.

You want to move from one spot on the map to another, but the direct path to your destination is blocked by the red circle, so you need to find a way around it. Can you find the shortest path that avoids all hazards by never leaving the blue or entering the red circle? Touching the boundaries of the circles is fine, as long as you do not cross them.

Input Format

The input consists of:

one line with two integers $x_cxc, y_cyc specifying your current location;$
one line with two integers $x_dxd, y_dyd specifying your destination;$
one line with three integers $x_b, y_b, r_bxb,yb,rb specifying the center and radius of the blue circle;$
one line with three integers $x_rxr , y_ryr , r_rrr specifying the center and radius of the red circle.$

All coordinates have an absolute value of at most $r_b, r_r le 1 0001≤rb,rr≤1000. The red circle is strictly inside the blue circle. Your current location and destination are strictly inside the blue circle and strictly outside of the red circle, and the direct path between them is blocked by the red circle.$

Output Format

Output the length of the shortest path that does not leave the blue or enter the red circle. The output must be accurate up to a relative or absolute error (whichever is lower) of $10^{-7}10−7.$

本题答案不唯一，符合要求的答案均正确

样例输入

样例输出

10.8112187742

题目来源

German Collegiate Programming Contest 2018

红色部分为所求的

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <string>
 5 #include <algorithm>
 6 #include <utility>
 7 #include <vector>
 8 #include <map>
 9 #include <queue>
10 #include <stack>
11 #include <cstdlib>
12 #include <cmath>
13 typedef long long ll;
14 #define lowbit(x) (x&(-x))
15 #define ls l,m,rt<<1
16 #define rs m+1,r,rt<<1|1
17 using namespace std;
18 #define pi acos(-1)
19 double sx,sy,ex,ey;
20 double rx,ry,rr;
21 double mx,my,mr;
22 double dist(double x1,double x2,double y1,double y2)
23 {
24     return sqrt(pow(x1-x2,2)+pow(y1-y2,2));
25 }//两点间的距离
26 int  main()
27 {
28     scanf("%lf%lf%lf%lf",&sx,&sy,&ex,&ey);
29     scanf("%lf%lf%lf",&mx,&my,&mr);
30     scanf("%lf%lf%lf",&rx,&ry,&rr);
31     double a=dist(sx,rx,sy,ry);
32     double b=sqrt(pow(a,2)-pow(rr,2));//切线
33     double c=dist(ex,rx,ey,ry);
34     double d=sqrt(pow(c,2)-pow(rr,2));//切线
35     double e=dist(sx,ex,sy,ey);
36     //A1,A2,A3是相应的圆心角
37     double A1=acos(rr/a);
38     double A2=acos(rr/c);
39     double A3=acos((a*a+c*c-e*e)/(2*a*c));
40     double A4=A3-A1-A2;
41     double f=A4*rr;//弧长
42     printf("%.10f
",f+b+d);
43     return 0;
44 }