XIV Open Cup named after E.V. Pankratiev. GP of America B.Bob and Banjo
题目大意
给你两个点和一个圆，要求穿过圆的任何一段路径都不超过 $t$ ，问最短路径长度是多少。保证两个点都不在圆内。
题目分析
首先，如果两个点的连线不经过圆，那么答案就是他们二者的距离。
考虑如果两个点的连线经过圆。那么显然应该是先走到圆，之后顺着圆的边上走，之后再离开圆走到终点。在如果固定在圆上的起始点和终止点，那么可以通过先不停的走长度为 $t$ 的割线来构造最短的路径。圆上的起始点和终止点的移动范围显然是每个点与圆的两条切线之间。而显然移动这两个点的时候会出现极小值。通过使用三分套三分即可解决。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
int n, m;
double eps = 1e-8;
double pi = 3.1415926535897932384626433;
double xa, xb, ya, yb, xc, yc, R, t;
int read(){
int x;
scanf("%d", &x);
return x;
}
double sqr(double x){
return x * x;
}
double dist(double x, double y, double a, double b){
return sqrt(sqr(x - a) + sqr(y - b));
}
bool cross(){
for(int i=0;i<=1e5;i++){
double x = (xb - xa) * (double)i / 1e5 + xa;
double y = (yb - ya) * (double)i / 1e5 + ya;
if(dist(x, y, xc, yc) - R <= eps){
return true;
}
}
return false;
}
double checkb(double a, double b){
double x = b - a;
double y = a - b;
double d = asin((t / 2.0) / R) * 2.0;
double ans = 0;
if(t - 2.0 * R >= eps){
return dist(xb, yb, xc + cos(b) * R, yc + sin(b) * R) + dist(xc + cos(a) * R, yc + sin(a) * R, xc + cos(b) * R, yc + sin(b) * R);
}
while(x - 2 * pi > eps)x -= 2 * pi;
while(x < eps)x += 2 * pi;
while(y - 2 * pi > eps)y -= 2 * pi;
while(y < eps)y += 2 * pi;
x = min(x, y);
if(t <= eps or d <= eps){
ans = R * x;
}else{
y = floor(x / d);
ans += y * t;
y = x - y * d;
ans += 2.0 * sin(y / 2.0) * R;
}
return dist(xb, yb, xc + cos(b) * R, yc + sin(b) * R) + ans;
}
double check(double a){
int i, j;
double l, r;
double midl, midr;
double d = acos((xb - xc) / dist(xb, yb, xc, yc));
if(yc - yb >= eps){
d = 2 * pi - d;
}
l = d - acos(R / dist(xb, yb, xc, yc));
r = d + acos(R / dist(xb, yb, xc, yc));
for(i=1;i<=100;i++){
midl = (2.0 * l + r) / 3.0;
midr = (l + 2.0 * r) / 3.0;
if(checkb(a, midl) < checkb(a, midr)){
r = midr;
}else{
l = midl;
}
}
return dist(xa, ya, xc + cos(a) * R, yc + sin(a) * R) + checkb(a, l);
}
int solve(){
int i, j;
double l, r;
double midl, midr;
double d = acos((xa - xc) / dist(xa, ya, xc, yc));
if(yc - ya >= eps){
d = 2 * pi - d;
}
l = d - acos(R / dist(xa, ya, xc, yc));
r = d + acos(R / dist(xa, ya, xc, yc));
for(i=1;i<=100;i++){
midl = (2.0 * l + r) / 3.0;
midr = (l + 2.0 * r) / 3.0;
if(check(midl) < check(midr)){
r = midr;
}else{
l = midl;
}
}
printf("%.6f\n", check(l));
return 0;
}
int main(){
int i, j;
while(~scanf("%lf%lf%lf%lf%lf%lf%lf%lf", &xa, &ya, &xb, &yb, &xc, &yc, &R, &t)){
if(xa == 0 and ya == 0 and xb == 0 and yb == 0 and xc == 0 and yc == 0 and R == 0 and t == 0){
break;
}
if(!cross()){
printf("%.6f\n", dist(xa, ya, xb, yb));
}else{
solve();
}
}
return 0;
}