BZOJ4077 : [Wf2014]Messenger

时间:2024-01-06 13:32:56

二分答案,让$A$推迟出发$mid$的时间。

对于每个相邻的时间区间,两个点都是做匀速直线运动。

以$A$为参照物,那么$A$不动,$B$作匀速直线运动。

若线段$B$到$A$的距离不超过$mid$,则可行。

时间复杂度$O(n\log n)$。

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=50010;
const double eps=1e-9;
inline int sgn(double x){
if(x<-eps)return -1;
if(x>eps)return 1;
return 0;
}
int n,m,i;double l,r,mid,f[N],da[N],db[N];
struct P{
double x,y;
P(){}
P(double _x,double _y){x=_x,y=_y;}
P operator+(const P&b){return P(x+b.x,y+b.y);}
P operator-(const P&b){return P(x-b.x,y-b.y);}
P operator*(double b){return P(x*b,y*b);}
P operator/(double b){return P(x/b,y/b);}
double operator*(const P&b){return x*b.x+y*b.y;}
double len(){return hypot(x,y);}
void read(){scanf("%lf%lf",&x,&y);}
}a[N],b[N];
inline double cross(P a,P b){return a.x*b.y-a.y*b.x;}
inline P lerp(P a,P b,double t){return a*(1.0-t)+b*t;}
inline double dist_point_to_segment(P p,P a,P b){
if((b-a).len()>eps&&sgn((p-a)*(b-a))>=0&&sgn((p-b)*(a-b))>=0)return fabs(cross(p-a,b-a))/(b-a).len();
return min((p-a).len(),(p-b).len());
}
inline double cal(P A,P B,P C,P D,double t){
B=B-A;
B=B/B.len();
D=D-C;
D=D/D.len();
D=D-B;
return dist_point_to_segment(A,C,C+D*t);
}
bool check(double mid){
int i=1,j;
P A=a[1],B;
double v=0,w;
for(j=1;j<m;j++)if(mid<f[j]){
w=mid-f[j-1];
B=lerp(b[j],b[j+1],w/db[j]);
break;
}
if(j==m)return 1;
while(i<n&&j<m){
double x=(A-a[i+1]).len(),y=(B-b[j+1]).len();
if((A-B).len()<mid+eps)return 1;
if(x>eps&&y>eps)if(cal(A,a[i+1],B,b[j+1],min(x,y))<mid+eps)return 1;
if(!sgn(x-y)){
A=a[++i];
B=b[++j];
v=w=0;
continue;
}
if(x<y){
A=a[++i];
v=0;
w+=x;
B=lerp(b[j],b[j+1],w/db[j]);
continue;
}
v+=y;
A=lerp(a[i],a[i+1],v/da[i]);
B=b[++j];
w=0;
}
return 0;
}
int main(){
scanf("%d",&n);
for(i=1;i<=n;i++)a[i].read();
scanf("%d",&m);
for(i=1;i<=m;i++)b[i].read();
for(i=1;i<n;i++)da[i]=(a[i]-a[i+1]).len();
for(i=1;i<m;i++)db[i]=(b[i]-b[i+1]).len();
for(i=1;i<m;i++)f[i]=f[i-1]+db[i];
r=f[m-1];
if((a[1]-b[m]).len()>r+eps)return puts("impossible"),0;
for(i=40;i;i--)if(check(mid=(l+r)/2))r=mid;else l=mid;
return printf("%.8f",(l+r)/2),0;
}