BZOJ 4077 Messenger

Messenger

【问题描述】

alice和bob各自在两条折线上行进，一个邮递员要从alice那拿一个包裹，并以直线移动到bob处，alice和bob、邮递员的速度均为1单位/s，问邮递员最少要走多少秒才能送完包裹。

【输入格式】

输入数据的第一行是一个整数na，代表alice运动轨迹的折线上的顶点数。

之后na行，每行两个整数，依次代表这个折线的第1号点、第2号点......第na号点的坐标。

之后一行是一个整数nb，代表bob运动轨迹的折线上的顶点数。

之后nb行，每行两个整数，依次代表这个折线的第1号点、第2号点......第nb号点的坐标。

na,nb目测是50000以内

【输出格式】

输出只有一行，一个小数，代表邮递员最少要走的时间。若无解，输出impossible

【样例输入】

2
0 0
0 10
2
4 10
4 0

【样例输出】

4.00000

题解：

考虑二分答案

让 Bob 提前走 mid，那么 Alice 与 Bob 的实时距离就是快递员要走的时间

Check时不断移动，移动的距离是两个人分别与下一个点的距离中的较小值

问题变成了求实时距离（两个人有速度，在不同线段上运动）的最小值

我们以 Alice 为参考系，Bob 匀速移动，并且距离是不变的

就变成了求点（Allice所在位置）到直线（Bob的移动轨迹）的距离、

那么用点积判断是否组成锐角三角形，是的话用叉积求投影，否则就是点与直线两端点的较小值

无解的话 Check( Bob 的总路程) 一下就可以了

 #include<cmath>

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 inline void Scan(int &x)

 {

     char c;

     bool o = false;

     while(!isdigit(c = getchar())) o = (c != '-') ? o : true;

     x = c - '';

     while(isdigit(c = getchar())) x = x *  + c - '';

     if(o) x = -x;

 }

 const int maxn = 1e5;

 const double inf = 2e10;

 const double eps = 1e-;

 struct point

 {

     double x, y;

     friend inline point operator + (point a, point b)

     {

         return (point) {a.x + b.x, a.y + b.y};

     }

     friend inline point operator - (point a, point b)

     {

         return (point) {a.x - b.x, a.y - b.y};

     }

     friend inline point operator * (point a, double x)

     {

         return (point) {a.x * x, a.y * x};

     }

     friend inline point operator / (point a, double x)

     {

         return (point) {a.x / x, a.y / x};

     }

     friend inline double operator * (point a, point b)

     {

         return a.x * b.y - a.y * b.x;

     }

     friend inline double operator ^ (point a, point b)

     {

         return a.x * b.x + a.y * b.y;

     }

     inline void print()

     {

         printf("x=%.2lf y=%.2lf\n", x, y);

     }

 };

 struct ele

 {

     int n;

     double t;

     point p;

     void print()

     {

         printf("n=%d t=%.2lf ", n, t);

         p.print();

     }

 };

 inline double Sqr(double x)

 {

     return x * x;

 }

 inline double Dis(point a, point b)

 {

     return sqrt(Sqr(a.x - b.x) + Sqr(a.y - b.y));

 }

 inline int Sgn(double x)

 {

     if(x < -eps) return -;

     if(x > eps) return ;

     return ;

 }

 inline double Dis(point a, point b, point c)

 {

     if(Sgn(Dis(b, c)))

         if(Sgn((a - b) ^ (c - b)) >=  && Sgn((a - c) ^ (b - c)) >= )

             return fabs(((a - b) * (c - b)) / Dis(b, c));

     return min(Dis(a, b), Dis(a, c));

 }

 struct thing

 {

     int n;

     point p[maxn];

     double s[maxn];

     inline void Read()

     {

         Scan(n);

         for(int i = ; i <= n; ++i)

         {

             scanf("%lf%lf", &p[i].x, &p[i].y);

             if(i > ) s[i] = s[i - ] + Dis(p[i], p[i - ]);

         }

     }

 };

 thing a, b;

 inline point Pos(bool o, double x, int p)

 {

     if(o) return b.p[p] + (b.p[p + ] - b.p[p]) * (x / (b.s[p + ] - b.s[p]));

     return a.p[p] + (a.p[p + ] - a.p[p]) * (x / (a.s[p + ] - a.s[p]));

 }

 point va, vb, dv;

 inline double Mini(point a, point b, point c, point d, double dis)

 {

     va = (b - a) / Dis(a, b);

     vb = (d - c) / Dis(c, d);

     dv = vb - va;

     d = c + dv * dis;

     return Dis(a, c, d);

 }

 inline bool Check(double mid)

 {

     ele u, v;

     u = (ele) {, , a.p[]};

     int n = upper_bound(b.s + , b.s +  + b.n, mid) - b.s - ;

     double s = mid - b.s[n];

     v = (ele) {n, s, Pos(true, s, n)};

     int x, y;

     double l, r, res;

     while(true)

     {

         if(Dis(u.p, v.p) < mid + eps) return true;

         if(u.n == a.n || v.n == b.n) break;

         x = u.n + , y = v.n + ;

         l = Dis(u.p, a.p[x]), r = Dis(v.p, b.p[y]);

         res = Mini(u.p, a.p[x], v.p, b.p[y], min(l, r));

         if(res < mid + eps) return true;

         if(!Sgn(l - r))

         {

             u = (ele) {x, , a.p[x]};

             v = (ele) {y, , b.p[y]};

             continue;

         }

         if(l < r)

         {

             u = (ele) {x, , a.p[x]};

             v.t += l;

             v.p = Pos(true, v.t, v.n);

         }

         else

         {

             u.t += r;

             u.p = Pos(false, u.t, u.n);

             v = (ele) {y, , b.p[y]};

         }

     }

     return false;

 }

 inline double Two()

 {

     int num = ;

     double mi;

     double l = , r = b.s[b.n];

     while(num--)

     {

         mi = (l + r) / 2.0;

         if(Check(mi)) r = mi;

         else l = mi;

     }

     if(Check(l)) return l;

     return r;

 }

 int main()

 {

     a.Read();

     b.Read();

     if(!(Check(b.s[b.n])))

     {

         printf("impossible\n");

         return ;

     }

     printf("%.5lf", Two());

 }

巴特西

BZOJ 4077 Messenger

最新文章

热门文章