[ICPC2014 WF] F Messenger 题解
首先需要证明答案满足单调性。
也就是说在一定范围内\(x\)满足要求，则\(\geq x\)的也满足要求。
具体证明方法如下：
可以将红线替换成蓝线使得答案更大。
然后还需要判断无解。
可以发现如果A可以在B之前到达某一个点，则一定是可以的。
那么只需要一开始就让A直线到B的终点，看是否在B之前就可判断是否有解。
然后考虑二分答案的部分。
判断\(x\)?是否可行。
可以先让\(B\)走\(x\)步然后一起走，询问是否存在一个时刻满足\(A,B\)的距离\(=x\)。
可以将\(B\)看成参考系，记录\(A\)的移动轨迹，然后求一下线段和点的距离即可。
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define check_min(a,b) a=min(a,b)
#define check_max(a,b) a=max(a,b)
using namespace std;
#define double long double
//inline int read(){
// int x=0;
// char ch=getchar();
// while(ch<‘0‘||ch>‘9‘){
// ch=getchar();
// }
// while(ch>=‘0‘&&ch<=‘9‘){
// x=(x<<1)+(x<<3)+(ch^48);
// ch=getchar();
// }
// return x;
//}
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
/*}
*/
const double eps=1e-8;
struct vec{
double x,y;
vec(){
x=y=0;
}
vec(double _,double __){
x=_;
y=__;
}
vec operator + (vec ano){
vec ret;
return vec(x+ano.x,y+ano.y);
}
vec operator - (vec ano){
vec ret;
return vec(x-ano.x,y-ano.y);
}
double operator * (vec ano){
return x*ano.y-y*ano.x;
}
double dot(vec ano){
return x*ano.x+y*ano.y;
}
};
vector<pair<vec,double> > A,B;
int n,m;
double getdis(double x,double y,double X,double Y){
return sqrt((X-x)*(X-x)+(Y-y)*(Y-y));
}
double getline(vec A,vec B){
double ans=min(getdis(A.x,A.y,0,0),getdis(B.x,B.y,0,0));
double s=abs((B-A)*(vec(0,0)-A));
if((vec(0,0)-A).dot(B-A)>-eps&&(vec(0,0)-B).dot(A-B)>-eps)
check_min(ans,s/getdis(A.x,A.y,B.x,B.y));
// cout<<A.x<<‘ ‘<<A.y<<‘ ‘<<B.x<<‘ ‘<<B.y<<‘ ‘<<ans<<endl;
return ans;
}
bool checkdis(vec st,vector<pair<vec,double> > walk,double t){
for(auto it:walk){
vec nx;
nx=st+vec(it.FIR.x*it.SEC,it.FIR.y*it.SEC);
if(getline(st,nx)<t+eps) return true;
st=nx;
}
return false;
}
vector<pair<vec,double> > merge(vector<pair<vec,double> > A,vector<pair<vec,double> > B){
int pt1=0,pt2=0;
vector<pair<vec,double> > ret;
while(pt1<A.size()&&pt2<B.size()){
double mn=min(A[pt1].SEC,B[pt2].SEC);
ret.PB(II(A[pt1].FIR-B[pt2].FIR,mn));
A[pt1].SEC-=mn;
B[pt2].SEC-=mn;
if(A[pt1].SEC<eps) pt1++;
if(B[pt2].SEC<eps) pt2++;
}
return ret;
}
double sx,sy;
double sx2,sy2;
bool check(double t){
//B walks t
vector<pair<vec,double> > BB;
double savet=t;
int pt=0;
vec nowb=vec(sx2,sy2);
while(pt<B.size()){
// cout<<B[pt].FIR.x<<"!"<<B[pt].FIR.y<<endl;
nowb=nowb+vec(B[pt].FIR.x*min(t,B[pt].SEC),B[pt].FIR.y*min(t,B[pt].SEC));
if(B[pt].SEC<=t){
t-=B[pt].SEC;
}
else{
BB.PB(II(B[pt].FIR,B[pt].SEC-t));
t=0;
}
++pt;
}
// cout<<nowb.x<<" "<<nowb.y<<endl;
vec nowa=vec(sx,sy);
nowa=nowa-nowb;
return checkdis(nowa,merge(A,BB),savet);
}
int main(){
scanf("%d",&n);
double x,y;
rb(i,1,n){
double nx,ny;
scanf("%Lf%Lf",&nx,&ny);
if(i!=1){
double dis=(nx-x)*(nx-x)+(ny-y)*(ny-y);
dis=sqrt(dis);
vec dir(nx-x,ny-y);
dir.x/=dis;
dir.y/=dis;
A.PB(II(dir,dis));
}
else{
sx=nx;
sy=ny;
}
x=nx,y=ny;
}
scanf("%d",&m);
double tot=0;
rb(i,1,m){
double nx,ny;
scanf("%Lf%Lf",&nx,&ny);
if(i!=1){
double dis=(nx-x)*(nx-x)+(ny-y)*(ny-y);
dis=sqrt(dis);
vec dir(nx-x,ny-y);
dir.x/=dis;
dir.y/=dis;
tot+=dis;
// cout<<dir.y<<"_"<<dir.x<<endl;
B.PB(II(dir,dis));
}
else{
sx2=nx;
sy2=ny;
}
x=nx,y=ny;
}
// cout<<check(0)<<endl;
// return 0;
if(tot<getdis(sx,sy,x,y)-eps){
puts("impossible");
return 0;
}
double l=0,r=tot;
rb(i,1,70){
double mid=(l+r)/2;
if(check(mid)) r=mid;
else l=mid;
}
printf("%.10Lf\n",l);
return 0;
}