题解 CF70D 【Professor's task】
这题居然搞了我一晚上。。。
首先题面的翻译并不清晰，如果仔细阅读英文原题会看到，询问的是点(x,y)是否在凸包内部（含边界），可能也只有我这种傻x一开始理解成了询问在不在凸包上，以及还有一句话没有翻译：所有加入集合S的点都不同。
然后来说这题怎么做。回顾我们求凸包的过程：先按坐标排序，然后先求个上凸壳，再求个下凸壳，围起来就是整个凸包。所以这题我们也可以用两个数据结构分别维护上凸壳和下凸壳。
考虑用平衡树来维护凸壳。以上凸壳为例。先不考虑一些边界之类的细节问题，加入一个点的时候，首先要判断它是否会产生影响，即如果它在现有的凸包内部（上凸壳的下方，下凸壳的上方）就直接退出。在已知它一定会加入凸包的情况下，考虑它左右的点是否会形成凹的图形，这里可以用叉积来判断。叉积一定要开long long！
比方说如果加入上凸壳的点P(x, y)，左边第一个点是A，第二个点是B，如果折线BAP向下凹就要删除A，然后继续这样做下去。对右边也这样做，然后对下凸壳也是一样。
具体的实现上，注意到因为我们是维护上凸壳和下凸壳，因此在一个凸壳上，所有的点的x坐标两两不同，因此我们可以用std::map<int, int>来维护，以横坐标为关键字，纵坐标为值。在迭代器的使用上要倍加小心，仔细考虑边界情况，具体可以看代码。
最后再介绍一下我在代码中使用的，令很多OIer深恶痛绝的std::next（以及它的兄弟std::prev）。自C++11起，头文件<iterator>中，命名空间std内新增了三个函数：std::advance, std::next, std::prev。其中std::next和std::prev都是转而调用std::advance。std::next接受两个参数，第一个是迭代器i，第二个是一个带符号整数n（默认为1），会返回一个迭代器，指向i往后移n的位置。std::prev也一样，唯一的区别是它往前移。作为一个看完了整本《C++Primer》的人，我表示C++Primer上并没有提到三个函数......我也是查了cppreference才知道。好在我从来都没有用bits/stdc++.h库和写using namespace std的习惯，因此从来没有因为next而CE过。。。
完整代码：
#include <cctype>
#include <cstdio>
#include <climits>
#include <algorithm>
#include <map>
#include <iterator>
template <typename T> inline void read(T& t) {
int f = 0, c = getchar(); t = 0;
while (!isdigit(c)) f |= c == '-', c = getchar();
while (isdigit(c)) t = t * 10 + c - 48, c = getchar();
if (f) t = -t;
}
template <typename T, typename... Args>
inline void read(T& t, Args&... args) {
read(t); read(args...);
}
#define rep(I, A, B) for (int I = (A); I <= (B); ++I)
#define rrep(I, A, B) for (int I = (A); I >= (B); --I)
#define erep(I, X) for (int I = head[X]; I; I = next[I])
std::map<int, int> up, down;
int n;
inline long long cross(int x1, int y1, int x2, int y2) {
return 1ll * x1 * y2 - 1ll * x2 * y1;
}
inline bool checkUp(int x, int y) {
auto pos = up.lower_bound(x);
if (pos == up.end()) return false;
if (pos->first == x) return y <= pos->second;
if (pos == up.begin()) return false;
auto prev = std::prev(pos);
return cross(x - prev->first, y - prev->second, pos->first - prev->first, pos->second - prev->second) >= 0;
}
inline bool checkDown(int x, int y) {
auto pos = down.lower_bound(x);
if (pos == down.end()) return false;
if (pos->first == x) return y >= pos->second;
if (pos == down.begin()) return false;
auto prev = std::prev(pos);
return cross(x - prev->first, y - prev->second, pos->first - prev->first, pos->second - prev->second) <= 0;
}
inline void insertUp(int x, int y) {
if (checkUp(x, y)) return;
up[x] = y;
auto pos = up.find(x);
auto next = std::next(pos);
if (next != up.end()) {
auto next2 = std::next(next);
while (next2 != up.end()) {
if (cross(next->first - x, next->second - y, next2->first - x, next2->second - y) >= 0) {
up.erase(next);
next = next2;
next2 = std::next(next2);
} else break;
}
}
if (pos == up.begin()) return;
auto prev = std::prev(pos);
while (prev != up.begin()) {
auto prev2 = std::prev(prev);
if (cross(prev->first - x, prev->second - y, prev2->first - x, prev2->second - y) <= 0) {
up.erase(prev);
prev = prev2;
} else break;
}
}
inline void insertDown(int x, int y) {
if (checkDown(x, y)) return;
down[x] = y;
auto pos = down.find(x);
auto next = std::next(pos);
if (next != down.end()) {
auto next2 = std::next(next);
while (next2 != down.end()) {
if (cross(next->first - x, next->second - y, next2->first - x, next2->second - y) <= 0) {
down.erase(next);
next = next2;
next2 = std::next(next2);
} else break;
}
}
if (pos == down.begin()) return;
auto prev = std::prev(pos);
while (prev != down.begin()) {
auto prev2 = std::prev(prev);
if (cross(prev->first - x, prev->second - y, prev2->first - x, prev2->second - y) >= 0) {
down.erase(prev);
prev = prev2;
} else break;
}
}
int main() {
read(n);
rep(i, 1, n) {
int q, x, y;
read(q, x, y);
if (q == 1) {
insertUp(x, y);
insertDown(x, y);
} else {
puts(checkUp(x, y) && checkDown(x, y) ? "YES" : "NO");
}
}
return 0;
}