牛客多校第三场 G 题题解

G Geometry

题意：给定两个 $nn$ 个点和 $mm$ 个点的凸包和运动方向，问是否会发生碰撞，何时发生碰撞。$3\le n,m\le 5\times 10^{4}3\; \backslash leq\; n,m\; \backslash leq\; 5\backslash times\; 10^4$。

解法：两个多边形速度为 $\overrightarrow{v_1},\overrightarrow{v_2}\backslash vec\{v\_1\},\backslash vec\{v\_2\}$ 等效于一个凸包以速度 $\overrightarrow{v_2}-\overrightarrow{v_1}\backslash vec\{v\_2\}-\backslash vec\{v\_1\}$ 运动。那么问题就转化为了两个凸包的闵氏和与射线 $(0,0)\to \overrightarrow{v_2}-\overrightarrow{v_1}(0,0)\; \backslash to\; \backslash vec\{v\_2\}-\backslash vec\{v\_1\}$ 有无交点，最近交点在哪里。此题与 https://www.luogu.com.cn/problem/P4557 很像。

db Solve() {
    int n, m;
    Poly a, b;
    scanf("%d", &n), a.resize(n);
    for (auto &p : a) scanf("%Lf%Lf", &p.x, &p.y);
    scanf("%d", &m), b.resize(m);
    for (auto &p : b) scanf("%Lf%Lf", &p.x, &p.y), p = {-p.x, -p.y};
    Vec v1, v2;
    scanf("%Lf%Lf%Lf%Lf", &v1.x, &v1.y, &v2.x, &v2.y);
    Line v = {{0, 0}, v2 - v1};
    a = mincowskySum(a, b), n = a.size();
    if (inHull(a, v.p, 0)) return 0;
    db ans = 1e18;
    for (int i = 0; i < n; ++i) {
        Seg s = {a[i], a[(i + 1) % n]};
        for (auto p : s.inter(v))
            if (p * v.v > 0)
                ans = min(ans, p.len());
    }
    if (ans > 1e17) return -1;
    return ans / v.v.len();
}