题目链接：Codeforces 70D
你需要实现这样一个数据结构，维护一个点集 $S$ 的凸包。一共有 $q$ 种操作，操作分为如下 $2$ 种：
- 将一个坐标为 $(x,y)$ 的点加入点集 $S$。点集 $S$ 的凸包可能会改变，也可能还是原来的样子。
- 查询点 $(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;
}