CF70D Professor's task 题解

前言

此篇题解用的是 \(Andrew\)，不想看这种做法的可以绕道。

题意

动态凸包板子题。

维护动态凸包。两种操作，加一个点或查询一个点是否在凸包内。

题解

维护二维凸包的方法挺多的，比如什么 \(Andrew\) 算法，\(Jarvis\) 算法还有 \(Graham\) 扫描法，极角法（当然我个人认为极角法不太好，掉精啥的麻烦），在二维凸包板子题的题解里里有一位大佬写的非常好，给个链接（会的可以略过此部分）。

我觉得 \(Andrew\) 好打还方便 ~~就会这一个~~ 所以这里用的 \(Andrew\) 算法。

考虑怎么维护动态的凸包。

对于查询，我们比较好办，只需要查一下它是不是在下凸壳上面并且在上凸壳下面，如果是，那就在里面，不是，则不在。

怎么查？向量积（叉乘）呗。\(check\) 函数不就出来了吗。

那怎么加点？

先想想静态凸包我们干了点什么：

以横坐标为第一关键字，纵坐标为第二关键字排了遍序；
每次叉乘判断是否加入一个新点；
加入的过程中弹出原来的不是最优的点。

所以我们现在也需要维护这些东西：

需要一直保证有序，于是选用 \(map\)，方便一会用指针遍历，也能保证有序；
加入新点也是一样的，还是叉乘判断；
弹出有点麻烦，不想原来那样打个指针走就行，这次得打个函数，因为我们需要维护那个 \(map\)。

就没了。

总结一下：\(check\) 函数，\(insert\) 函数，\(remove\) 函数，上凸壳和下凸壳都各自需要这三个函数，所以总共是 \(6\) 个。具体细节见代码。

说一下时间复杂度。

第一篇题解的时间复杂度讲的有点，，，反正我猛一下没看懂，但是还是比较好分析的。

每一个点最多都会加一次再弹出一次，单次加进去和单次弹出都是 \(O(logn)\)，于是总的就是 \(O(nlogn)\)。

代码

//https://www.luogu.com.cn/problem/CF70D CF70D Professor's task
#include <bits/stdc++.h>
#define int long long
#define P pair<int, int>
#define MP make_pair

using namespace std;

int n;
map<int, int> top, bottom;

P operator - (P x, P y) {return {y.first - x.first, y.second - x.second};}

inline int cross(P x, P y) {return x.first * y.second - x.second * y.first;}

inline bool check_top (int x, int y) {
    auto pos = top.lower_bound(x);
    if(pos == top.end())
        return false;
    if(pos -> first == x)
        return y <= pos -> second;
    if(pos == top.begin())
        return false;
    auto pre = pos;
    -- pre;
    return cross(MP(pre -> first, pre -> second) - MP(pos -> first, pos -> second), MP(pre -> first, pre -> second) - MP(x, y)) <= 0;
}

inline bool check_bottom(int x, int y) {
    auto pos = bottom.lower_bound(x);
    if(pos == bottom.end())
        return false;
    if(pos -> first == x)
        return y >= pos -> second;
    if(pos == bottom.begin())
        return false;
    auto pre = pos;
    -- pre;
    return cross(MP(pre -> first, pre -> second) - MP(pos -> first, pos -> second), MP(pre -> first, pre -> second) - MP(x, y)) >= 0;
}

inline bool remove_top(map<int, int>::iterator pos) {
    if(pos == top.begin())
        return false;
    auto pre = pos, nex = pos;
    -- pre, ++ nex;
    if(nex == top.end())
        return false;
    if(cross(MP(pre -> first, pre -> second) - MP(pos -> first, pos -> second), MP(pre -> first, pre -> second) - MP(nex -> first, nex -> second)) < 0)
        return false;
    top.erase(pos);
    return true;
}

inline bool remove_bottom(map<int, int>::iterator pos) {
    if(pos == bottom.begin())
        return false;
    auto pre = pos, nex = pos;
    -- pre, ++ nex;
    if(nex == bottom.end())
        return false;
    if(cross(MP(pre -> first, pre -> second) - MP(pos -> first, pos -> second), MP(pre -> first, pre -> second) - MP(nex -> first, nex -> second)) > 0)
        return false;
    bottom.erase(pos);
    return true;
}

inline void add_top(int x, int y) {
    if(check_top(x, y))
        return;
    top[x] = y;
    auto pos = top.find(x), ji = pos;
    if(pos != top.begin()) {
        -- ji;
        while(remove_top(ji ++))
            -- ji;
    }
    if(++ ji != top.end())
        while(remove_top(ji --))
            ++ ji;
}

inline void add_bottom(int x, int y) {
    if(check_bottom(x, y))
        return;
    bottom[x] = y;
    auto pos = bottom.find(x), ji = pos;
    if(pos != bottom.begin()) {
        -- ji;
        while(remove_bottom(ji ++))
            -- ji;
    }
    if(++ ji != bottom.end())
        while(remove_bottom(ji --))
            ++ ji;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; ++ i) {
        int op, x, y;
        cin >> op >> x >> y;
        if(op == 1) {
            add_top(x, y);
            add_bottom(x, y);
        }
        else {
            if(check_top(x, y) && check_bottom(x, y))
                cout << "YES\n";
            else
                cout << "NO\n";
        }
    }
}