「JSOI2018」战争 题解

---

• 题目链接: https://www.luogu.com.cn/problem/P4557

这是一道 九条可怜 计算几何题, 在思路上不算困难但是有一些细节值得留念.

前置知识

1. 二维凸包
2. 闵可夫斯基和

题目大意

给定两个大小分别为 $n, m$ 的点集, $q$ 次询问, 每次给出一个偏移向量 $\vec{v}$, 问将第二个点集的所有点按这个向量偏移后, 是否存在一个点, 在另一点集的凸包内.

其中 $3 \le n, m \le 10^5, q \le 10^5$

题目思路

考虑最简单的思路, 每次直接将第二个点集暴力平移, 求凸包, 判断是否存在一个点在另一个凸包内.

时间复杂度 $O(n \log n + q (m \log m + n m)\,)$, 期望得分 40 pts.

如果再加一些技巧, 大概是 $O(n \log n + m\log m + q(n\log m + m\log n))\,)$, 期望得分 40 pts, 并没有本质区别…

换一种思路, 考虑造成冲突的向量范围, 容易得到这样的式子

$$\exists \ \vec{v},\ \text{s.t.}\ b + \vec{v} = a\ (a \in A, b \in B)$$

那么就可以得到 $\vec{v}$ 的范围

$$\vec{v} = a - b\ (a \in A, b \in B)$$

把 $B$ 中点的横纵坐标取反, 就得到了闵可夫斯基和的形式.

考虑到两个凸包的闵可夫斯基和中的边都由两个凸包中的边构成, 而凸包上的边具有单调性, 直接以类似于合并两个有序表的方式进行合并就好了, 这样合并出来的闵可夫斯基和也是个凸包.

如何统计答案呢? 直接判断偏移向量是否在闵可夫斯基和中的时间复杂度是 $O(n)$ 的, 可以拿到 70 pts 的好成绩.
考虑把一个凸包转化为一点到其他点的向量的形式, 这样判断一个向量是否在凸包内可以根据凸包的单调性, 通过二分查找解决.

代码实现

如果细节明确了, 其实代码不难写…

// Luogu P4557
// DeP
#include <cmath>
#include <cctype>
#include <cstdio>
#include <algorithm>
using namespace std;

namespace IO {
    const int MAXSIZE = 1 << 18 | 1;
    char buf[MAXSIZE], *p1, *p2;

    inline int Gc() {
        return p1 == p2 &&
            (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2)? EOF: *p1++;
    }
    template<typename T> inline void read(T& x) {
        x = 0; int f = 0, ch = Gc();
        while (!isdigit(ch)) f |= ch == '-', ch = Gc();
        while (isdigit(ch)) x = x * 10 + ch - '0', ch = Gc();
        if (f) x = -x;
    }
}
using IO::read;

typedef long long LL;
const int MAXN = 1e5+5;

namespace Geo {
    struct Vector {
        LL x, y;
        Vector(LL _x = 0, LL _y = 0): x(_x), y(_y) { }

        Vector operator + (const Vector& rhs) const { return Vector(x + rhs.x, y + rhs.y); }
        Vector operator - (const Vector& rhs) const { return Vector(x - rhs.x, y - rhs.y); }
    };
    typedef Vector Point;

    bool operator < (const Point& A, const Point& B) {
        return A.x < B.x || (A.x == B.x && A.y < B.y);
    }
    bool operator== (const Point& A, const Point& B) { return !(A < B) && !(B < A); }

    inline LL Dot(const Vector& A, const Vector& B) { return A.x * B.x + A.y * B.y; }
    inline LL Cross(const Vector& A, const Vector& B) { return A.x * B.y - A.y * B.x; }

    int ConvexHull(Point* P, int n, Point* ch) {
        int m = 0;
        sort(P, P+n);
        for (int i = 0; i < n; ++i) {
            while (m > 1 && Cross(ch[m-1] - ch[m-2], P[i] - ch[m-2]) <= 0) --m;
            ch[m++] = P[i];
        }
        int k = m;
        for (int i = n-2; i >= 0; --i) {
            while (m > k && Cross(ch[m-1] - ch[m-2], P[i] - ch[m-2]) <= 0) --m;
            ch[m++] = P[i];
        }
        return m - (n > 1);
    }
}
using namespace Geo;

int n, m, pidx, K;
Point poly[MAXN << 1];
Vector v1[MAXN], v2[MAXN];
Point P1[MAXN], P2[MAXN], ch1[MAXN], ch2[MAXN];

// 通俗地说, 凸包上的边, 在右侧的边总是在左侧的边的 "左侧"
// 还要考虑向量的模长, 可能太长就冲出去了...
inline bool cmp(const Point& A, const Point& B) {
    return Cross(A, B) > 0 || (Cross(A, B) == 0 && Dot(A, A) < Dot(B, B));
}

inline bool inPoly(const Vector& v) {
    if (Cross(v, poly[0]) > 0 || Cross(v, poly[pidx-1]) < 0) return 0;
    int pos = lower_bound(poly, poly+pidx, v, cmp) - poly - 1;
    return Cross(v - poly[pos], poly[(pos+1)%pidx] - poly[pos]) <= 0;
}

int main() {
#ifndef ONLINE_JUDGE
    // freopen("input.in", "r", stdin);
#endif
    // input
    read(n), read(m), read(K);
    for (int x, y, i = 0; i < n; ++i)
        read(x), read(y), P1[i] = Point(x, y);
    for (int x, y, i = 0; i < m; ++i)
        read(x), read(y), P2[i] = Point(-x, -y);
    // solve
    n = ConvexHull(P1, n, ch1);
    m = ConvexHull(P2, m, ch2);
    // 将凸包的点集转化为边集, 以向量的形式体现
    ch1[n] = ch1[0];
    for (int i = 0; i < n; ++i) v1[i] = ch1[i+1] - ch1[i];
    ch2[m] = ch2[0];
    for (int i = 0; i < m; ++i) v2[i] = ch2[i+1] - ch2[i];
    // Minkowski Sum
    // 合并两个凸包, 由于凸包单调性, 类似于合并两个有序表
    poly[pidx++] = ch1[0] + ch2[0];
    int p = 0, q = 0;
    while (p < n && q < m) {
        if (Cross(v1[p], v2[q]) >= 0)
            poly[pidx] = poly[pidx-1] + v1[p++], ++pidx;
        else poly[pidx] = poly[pidx-1] + v2[q++], ++pidx;
    }
    while (p < n) poly[pidx] = poly[pidx-1] + v1[p++], ++pidx;
    while (q < m) poly[pidx] = poly[pidx-1] + v2[q++], ++pidx;
    while (pidx > 1 &&
        Cross(poly[pidx-1] - poly[pidx-2], poly[0] - poly[pidx-2]) <= 0) --pidx;
    // 将闵可夫斯基和的点集转化为由一点指向其他点的向量
    Point o = poly[0];
    for (int i = 0; i < pidx; ++i) poly[i] = poly[i] - o;
    // output
    while (K--) {
        static int x, y;
        read(x), read(y), printf("%d\n", inPoly(Vector(x, y) - o));
    }
    return 0;
}

---