CF70D Professor's task（动态凸包模板）

· · 个人记录

题意

维护一个凸包，支持加点，询问一个点在不在凸包内

做法

有两种做法（大概）

用极角序得到凸包：选取的原点需要在凸包内才行，选取最开始的三个点的重心作为原点（然后给每个点坐标乘3以消除误差），然后用个首尾相连的set维护每条向量就行了

用水平序得到凸包：同时维护上下凸壳，用map[x]表示x坐标对应的纵坐标，然后每次分上下各搞一下就行了（P.S. map的lower_bound是以key为关键字的）

后者太难写了，于是写的极角序的

这样大概还不能维护带删除操作的。。。

#include<bits/stdc++.h>
#define IT set<pts>::iterator
using namespace std;
typedef long long ll;
int n;
struct pts
{
    ll x,y; double k;
    pts() { }
    pts(ll x,ll y,double k=0.0) : x(x),y(y),k(k) { }
    pts operator + (const pts &a)const { return pts(x + a.x,y + a.y); }
    pts operator - (const pts &a)const { return pts(x - a.x,y - a.y); }
    double operator ^ (const pts &a)const { return x * a.y - y * a.x; }
    bool operator < (const pts &a)const
    {
        return k != a.k ? k < a.k : x < a.x;
    }
}pt[4],o;
set<pts> S;
IT pre,suf;

inline IT Pre(IT it) { return it == S.begin() ? --S.end() : --it; }
inline IT Suf(IT it) { return (++it) == S.end() ? S.begin() : it; }
inline bool in(pts p) { return ((p - *pre) ^ (*suf - p)) <= 0; }
inline void ins(pts p)
{
    if(in(p)) return;
    S.insert(p);
    IT cur = S.find(p),las = Pre(cur),llas = Pre(las);
    while((int)S.size() >= 3 && ((*llas - *las) ^ (*las - *cur)) <= 0) S.erase(las),las = llas,llas = Pre(las);
    las = Suf(cur); llas = Suf(las);
    while((int)S.size() >= 3 && ((*llas - *las) ^ (*las - *cur)) >= 0) S.erase(las),las = llas,llas = Suf(las);
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=3;++i)
    {
        int op; ll x,y;
        scanf("%d%lld%lld",&op,&x,&y);
        o.x += x; o.y += y;
        pt[i] = pts(x * 3,y * 3);
    }
    for(int i=1;i<=3;++i) pt[i].k = atan2(pt[i].y - o.y,pt[i].x - o.x),S.insert(pt[i]);
    n -= 3;
    while(n--)
    {
        int op; ll x,y;
        scanf("%d%lld%lld",&op,&x,&y);
        x *= 3; y *= 3;
        pts p = pts(x,y,atan2(y - o.y,x - o.x));
        suf = S.lower_bound(p);
        if(suf == S.end()) suf = S.begin();
        pre = Pre(suf);
        if(op == 1) ins(p);
        else puts(in(p) ? "YES" : "NO");
    }
    return 0;
}