题目概述

动态加点维护凸包，每次询问 $(x,y)$ 是否在凸包中。

解题报告

终于写了下动态凸包……其实就是用set维护凸包中的点，动态做Andrew算法。

我用的是水平序，维护上下两个凸壳（这里有技巧，维护上凸壳时使用原坐标 $(x,y)$ ，而维护下凸壳时使用 $(x,-y)$ ，这样两个set的维护方式以及查询方式就完全一致了）。为了方便，对于 $x$ 坐标相同的点，我只保留了 $y$ 最大的，也就是说维护出来的两个凸壳不一定能凑成完整的凸包（可能缺少两边的竖线），不过问题不大。

查询的时候只需要在set中找到前驱后继，判断 $(x,y)$ 是否在前驱后继连线的下方，用直线方程或者叉积判断都行。

示例程序

#include<set>
#include<cstdio>
#include<algorithm>
#define X first
#define Y second
#define mp make_pair
using namespace std;
typedef long long LL;
typedef pair<int,int> vec;

int te;set<vec> A,B;set<vec>::iterator L,R;

inline vec operator - (const vec &a,const vec &b) {return mp(b.X-a.X,b.Y-a.Y);}
inline LL Cross(const vec &a,const vec &b) {return (LL)a.X*b.Y-(LL)a.Y*b.X;}
bool check(set<vec> &s,vec a){
    L=s.lower_bound(a);if (L==s.end()) return false;
    if ((*L).X==a.X) return true;if (L!=s.begin() && (*--L).X==a.X) return false;
    if (a.X<(*L).X) return false;R=L;R++;return Cross(*R-*L,a-*L)<=0;
}
void Insert(set<vec> &s,vec a){
    if (check(s,a)) return;
    L=s.lower_bound(a);if (L!=s.begin() && (*--L).X==a.X) s.erase(L);
    R=s.lower_bound(a);
    if (R!=s.begin() && (L=R,L--)!=s.begin())
        while (L!=s.begin()) {R=L;L--;if (Cross(*R-*L,a-*L)>=0) s.erase(R);}
    L=s.lower_bound(a);
    if (L!=s.end() && (R=L,R++)!=s.end())
        while (R!=s.end()) {if (Cross(*L-*R,a-*R)<=0) s.erase(L);L=R;R++;}
    s.insert(a);
}
int main(){
    freopen("70D.in","r",stdin);freopen("70D.out","w",stdout);
    for (scanf("%d",&te);te;te--){
        int tp,x,y;scanf("%d%d%d",&tp,&x,&y);
        if (tp==1) Insert(A,mp(x,y)),Insert(B,mp(x,-y));
        else puts(check(A,mp(x,y)) && check(B,mp(x,-y))?"YES":"NO");
    }
    return 0;
}