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";
}
}
}