「Codeforces 70D」Professor's Task

题目链接:Codeforces 70D

你需要实现这样一个数据结构,维护一个点集 $S$ 的凸包。一共有 $q$ 种操作,操作分为如下 $2$ 种:

  1. 将一个坐标为 $(x,y)$ 的点加入点集 $S$。点集 $S$ 的凸包可能会改变,也可能还是原来的样子。
  2. 查询点 $(x,y)$ 是否在凸包内部,包括边界。

保证前 $3$ 个操作都是加入操作,且加入的 $3$ 个点构成三角形。所有加入 $S$ 的点的坐标都是不同的。

数据范围:$4\le q\le 10^5$,$-10^6\le x,y\le 10^6$。


Solution

本题需要我们半动态维护凸包,支持查询和插入操作。我们将这个凸包看作 $2$ 个部分:上凸壳 + 下凸壳。于是接下来只考虑上凸壳这个部分,下凸壳同理。

由于凸包的性质,对于任何一个 $x$,存在至多 $1$ 个凸壳上的点满足其横坐标为 $x$。我们用 $\text{map}$ 维护凸壳上横坐标为 $x$ 的点的纵坐标。无论是加入还是查询,首先都要查询这个点是否在上凸壳下方,是否在下凸壳上方。同样我们只考虑上凸壳。

假设插入或查询的点为 $(x,y)$,如果 $\text{map}$ 中存在 $x$ 则直接比较 $y$ 的值;否则我们在 $\text{map}$ 中二分得到第一个大于 $x$ 的映射,最后一个小于 $x$ 的映射,利用向量叉积计算点 $(x,y)$ 和线段的关系。

考虑插入操作,假如 $(x,y)$ 在凸包外侧则需要更新凸包。假设上凸壳包含的点为 $(x_1,y_1),(x_2,y_2),\cdots,(x_m,y_m)$,那么我们还是按照查询的方法二分找到点 $(x_k,y_k),(x_{k+1},x_{k+1})$,然后从 $(x_k,y_k)$ 往前枚举所有相邻的点,如果点 $(x,y)$ 在有向线段 $(x_{i-1},y_{i-1}),(x_i,y_i)$ 左侧(叉积为正)那么删除点 $(x_i,y_i)$。对于点 $(x_{k+1},y_{k+1})$ 同理向后枚举相邻的点进行相同操作。一旦不能删除即退出,注意记得在删除之后加入点 $(x,y)$!

由于每个点至多被加入 $1​$ 次,删除 $1​$ 次,因此复杂度正确。

向量叉积:在此提一下向量叉积判断点和向量(也就有向线段)的关系。如果我们有点 $A,B,C$,需要判断 $C$ 和有向线段 $AB$ 的位置关系。构造向量 $\vec{v_1}=\vec{AC},\vec{v_2}=\vec{BC}$,如果 $\vec{v_1}\times\vec{v_2}>0$ 则点 $C$ 在向量 $\vec{AB}$ 的左侧;如果 $\vec{v_1}\times\vec{v_2}<0$ 则点 $C$ 在向量 $\vec{AB}$ 的右侧;如果 $\vec{v_1}\times\vec{v_2}=0$ 则点 $C$ 在向量 $\vec{AB}​$ 所在的直线上。

时间复杂度:$\mathcal O(q\log q)$。


Code

#include <cstdio>
#include <algorithm>
#include <map>

typedef long long LL;
typedef std::map<int, int>::iterator iter;

int n;
std::map<int, int> mp1, mp2;

template <typename Tp> struct Point {
    Tp x, y;
    Point(Tp _x = 0, Tp _y = 0) {
        x = _x, y = _y;
    }
    Point operator+(const Point &b) const {
        return Point(x + b.x, y + b.y);
    }
    Point operator-(const Point &b) const {
        return Point(x - b.x, y - b.y);
    }
    Tp operator*(const Point &b) const {
        return x * b.x + y * b.y;
    }
    Tp operator^(const Point &b) const {
        return x * b.y - y * b.x;
    }
};

template <typename Tp> Tp cross(Point<Tp> a, Point<Tp> b, Point<Tp> x) {
    return (x - a) ^ (x - b);
}
iter Last(iter x) { return --x; }
iter Next(iter x) { return ++x; }
template <typename Tp> bool check(Point<Tp> a, std::map<int, int> &mp, int type) {
    if (mp.count(a.x)) return type * mp[a.x] >= type * a.y;
    iter r = mp.lower_bound(a.x);
    if (r == mp.begin() || r == mp.end()) return 0;
    std::map<int, int>::iterator l = Last(r);
    Point<LL> p = Point<LL>(l->first, l->second);
    Point<LL> q = Point<LL>(r->first, r->second);
    if (type * cross(p, q, a) <= 0) return 1;
    return 0;
}
template <typename Tp> void ins(Point<Tp> a, std::map<int, int> &mp, int type) {
    iter r = mp.lower_bound(a.x);
    if (r != mp.end()) {
        while (1) {
            iter t = Next(r);
            if (t == mp.end()) break;
            Point<LL> p = Point<LL>(r->first, r->second);
            Point<LL> q = Point<LL>(t->first, t->second);
            if (type * cross(p, q, a) >= 0) ++r, mp.erase(Last(r));
            else break;
        }
    }
    if (r != mp.begin()) {
        iter l = Last(r);
        while (1) {
            if (l == mp.begin()) break;
            iter t = Last(l);
            Point<LL> p = Point<LL>(t->first, t->second);
            Point<LL> q = Point<LL>(l->first, l->second);
            if (type * cross(p, q, a) >= 0) --l, mp.erase(Next(l));
            else break;
        }
    }
    mp[a.x] = a.y;
}
int main() {
    int q;
    scanf("%d", &q);
    while (q--) {
        int opt;
        Point<LL> a;
        scanf("%d%lld%lld", &opt, &a.x, &a.y);
        bool f1 = check(a, mp1, 1), f2 = check(a, mp2, -1);
        if (opt == 1) {
            if (!f1) ins(a, mp1, 1);
            if (!f2) ins(a, mp2, -1);
        } else {
            puts(f1 && f2 ? "YES" : "NO");
        }
    }
    return 0;
}

发表评论