P6897题解

· · 题解

Link

[ICPC2014 WF]Messenger

Solution

咳咳咳，为啥ICPC这么喜欢几何题

言归正传，我们分析下这道题目。

显然这题的计算几何部分不是重点，那么我们主要分析这个运动过程。

题目中是两个人同时在运动，然后随便分析一下，我们就可以看出：由于两个人都是匀速直线运动，那么我们直接将一个人选作参考系，就可以转化为只有一个人运动。

那么现在问题已经弱化很多了，可是还是不是非常好处理。

一个关键的想法：这个送邮递的过程，可以这样转化一下。我们不妨直接把邮递员这个工具人直接删了，把这个过程转换为Nadia提前了t出发，那么，在这种情况下，只要Misha（现在一直在原点）到Nadia路径的任何一段距离小于t，那么t的送货时间就是可行的。

然后就是一些细节问题。由于每次涉及到提前一个人，所以每次的相对路径需要重新计算。然后由于是浮点数，需要注意一下精度问题。但凡涉及到浮点数的题目我必定要交两三面。最终复杂度 \mathcal{O}(n\log n)。

Code

#include <cstdio>
#include <cmath>

#define _N 50010
#define _EPS 1e-8

struct Tuple {
    double x, y;
    Tuple() {
        x = y = 0;
    }
    Tuple(double a, double b) {
        x = a, y = b;
    }
};

Tuple inline operator +(const Tuple& left, const Tuple& right) {
    return Tuple(left.x + right.x, left.y + right.y);
}
Tuple inline operator -(const Tuple& left, const Tuple right) {
    return Tuple(left.x - right.x, left.y - right.y);
}
Tuple inline operator *(const Tuple& left, double right) {
    return Tuple(left.x * right, left.y * right);
}
double inline operator *(const Tuple& left, const Tuple& right) {
    return left.x * right.x + left.y * right.y;
}
Tuple inline operator /(const Tuple& left, double right) {
    return Tuple(left.x / right, left.y / right);
}
double inline operator %(const Tuple& left, const Tuple& right) {
    return left.x * right.y - left.y * right.x;
}

typedef Tuple Point;
typedef Tuple Vec;

int n, m;

Point misha[_N];
Point nadia[_N];
double disn[_N];

int inline sgn(double val) {
    if (val > _EPS) {
        return 1;
    }
    if (val < -_EPS) {
        return -1;
    }
    return 0;
}

double inline dist(Point left, Point right) {
    return sqrtl((right.x - left.x) * (right.x - left.x) + (right.y - left.y) * (right.y - left.y));
}
double inline len(Vec val) {
    return sqrtl(val.x * val.x + val.y * val.y);
}
double inline dist(Point p, Point left, Point right) {
    double len = dist(left, right);
    if (len > _EPS && sgn((p - left) * (right - left)) >= 0 && sgn((p - right) * (left - right)) >= 0) {
        return fabsl((p - left) % (right - left)) / len;
    }
    return fminl(dist(p, left), dist(p, right));
}
Point inline at(Point from, Point to, double len) {
    return from + (to - from) * len / dist(from, to);
}
Vec inline unit(Vec val) {
    return val / len(val);
}

bool check(double delay) {
    int ptm = 1, ptn = 1;
    double remm = 0, remn = delay;
    Point lastm = misha[1], lastn;
    while (ptn < m && disn[ptn] < delay + _EPS) {
        ptn++;
    }
    if (ptn == m) {
        return true;
    }
    remn -= disn[ptn - 1];
    lastn = at(nadia[ptn], nadia[ptn + 1], remn);
    while (ptm < n && ptn < m) {
        if (dist(lastm, lastn) < delay + _EPS) {
            return true;
        }
        double timm = dist(lastm, misha[ptm + 1]), timn = dist(lastn, nadia[ptn + 1]);
        Vec relamov = (unit(nadia[ptn + 1] - lastn) - unit(misha[ptm + 1] - lastm)) * fminl(timm, timn);
        if (timm > _EPS && timn > _EPS && dist(lastm, lastn, lastn + relamov) < delay + _EPS) {
            return true;
        }
        int cmp = sgn(timm - timn);
        if (cmp == 1) {
            remm += timn, remn = 0;
            lastm = at(misha[ptm], misha[ptm + 1], remm), lastn = nadia[++ptn];
        } else if (cmp == -1) {
            remn += timm, remm = 0;
            lastn = at(nadia[ptn], nadia[ptn + 1], remn), lastm = misha[++ptm];
        } else {
            remm = remn = 0;
            lastm = misha[++ptm], lastn = nadia[++ptn];
        }
    }
    return false;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lf%lf", &misha[i].x, &misha[i].y);
    }
    scanf("%d", &m);
    for (int i = 1; i <= m; i++) {
        scanf("%lf%lf", &nadia[i].x, &nadia[i].y);
    }
    for (int i = 1; i < m; i++) {
        disn[i] = dist(nadia[i], nadia[i + 1]);
        disn[i] += disn[i - 1];
    }
    double l = 0, r = disn[m - 1];
    if (dist(misha[1], nadia[m]) > r + _EPS) {
        puts("impossible");
        return 0;
    }
    while (r - l > _EPS) {
        double mid = (l + r) / 2;
        if (check(mid)) {
            r = mid;
        } else {
            l = mid;
        }
    }
    printf("%.4lf\n", (l + r) / 2);
    return 0;
}

Inspiration

我认为这题的转化如果是第一次接触还是有点难度的，不过其他的部分都不难。

关键结论：