【CF#8D】Two Friends

  • 本文为博主原创,未经许可不得转载

设$L1=t1+dis(A,B)$,$L2=t2+dis(A,C)+dis(B,C)$

如果$L1>=dis(A,C)+dis(B,C)$,那么答案显然就是$min(L1,L2)$

否则,我们可以二分一个$mid$,设分离点为$P$

那么$mid$合法的条件如下:

$dis(A,P)<=mid$

$dis(B,P)+dis(B,C)+mid<=L2$

$dis(C,P)+mid<=L1$

这实际上是三个圆

只需要判断这三个圆有没有公共部分即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<bits/stdc++.h>
#define FILE "read"
#define eps 1e-10
#define INF 1e9
using namespace std;
const double pi=acos(-1);
struct Point{
double x,y;
Point(double a=0,double b=0):x(a),y(b){}
inline void read(){scanf("%lf%lf",&x,&y);}
inline void print(){printf("%.2lf %.2lf\n",x,y);}
inline Point operator+(const Point &b){return Point(x+b.x,y+b.y);}
inline Point operator-(const Point &b){return Point(x-b.x,y-b.y);}
inline Point operator*(const double p){return Point(x*p,y*p);}
inline Point operator/(const double p){return Point(x/p,y/p);}
inline Point operator==(const Point &b){return fabs(x-b.x)<eps&&fabs(y-b.y)<eps;}
inline Point operator< (const Point &b){return x<b.x||(x==b.x&&y<b.y);}
inline double ang(){return atan2(y,x);}
}A,B,C;
struct Interval{
double l,r;
Interval(double a=0,double b=0):l(a),r(b){}
inline bool In_Interval(double x){return x>=l&&x<=r;}
};
struct Circle{
Point O; double r;
Circle(){}
Circle(Point O,double r):O(O),r(r){}
inline Point point(double rad){return Point(O.x+r*cos(rad),O.y+r*sin(rad));}
};
double t1,t2,L1,L2;
inline double Dot(Point A,Point B){return A.x*B.x+A.y*B.y;}
inline double Lenth(Point A){return sqrt(Dot(A,A));}
Interval Circle_Jiao(Circle c1,Circle c2){
double a=c1.r;
double b=c2.r;
double c=Lenth(c1.O-c2.O);
double temp=(c1.O-c2.O).ang();
double delta=acos((a*a+c*c-b*b)/(2*a*c));
return Interval(temp-delta,temp+delta);
}
bool Separate(Circle c1,Circle c2){
return Lenth(c1.O-c2.O)>c1.r+c2.r+eps;
}
bool Contain(Circle c1,Circle c2){
return Lenth(c1.O-c2.O)<fabs(c1.r-c2.r);
}
bool Interval_Jiao(Interval l1,Interval l2){
return l1.In_Interval(l2.l)||l1.In_Interval(l2.r)||l2.In_Interval(l1.l)||l2.In_Interval(l1.r);
}
bool Judge(Circle c1,Circle c2,Circle c3){
Interval l1=Circle_Jiao(c1,c2);
Interval l2=Circle_Jiao(c1,c3);
if(Interval_Jiao(l1,l2)) return 1;
return 0;
}
bool check(double mid){
Circle c1(A,mid);
Circle c2(B,L1-mid);
Circle c3(C,L2-Lenth(B-C)-mid);
if(Separate(c1,c2)||Separate(c1,c3)||Separate(c2,c3)) return 0;
if(Contain(c1,c2)||Contain(c1,c3)||Contain(c2,c3)) return 1;
if(Judge(c1,c2,c3)||Judge(c2,c1,c3)||Judge(c3,c1,c2)) return 1;
return 0;
}
void solve(){
double l=0,r=min(L1,L2-Lenth(B-C));
while(l+eps<r){
double mid=(l+r)/2;
if(check(mid)) l=mid;
else r=mid;
}
printf("%.10lf\n",check(r)?r:l);
}
int main(){
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
scanf("%lf%lf",&t2,&t1);
A.read(); B.read(); C.read();
L1=t1+Lenth(A-B);
L2=t2+Lenth(A-C)+Lenth(B-C);
if(L1>=Lenth(A-C)+Lenth(B-C)) printf("%.10lf\n",min(L1,L2));
else solve();
return 0;
}
文章目录
,