Codeforces 70D. Professor's task

题目链接：D - Professor's task

题目大意：初始给三个点，之后要求实现两种操作：加点；判断给定点是否在凸包内部。

动态凸包板子题，留档怕忘了，参考 https://www.cnblogs.com/enzymii/p/8413480.html

#include<bits/stdc++.h>
using namespace std;
#define N 100010
#define LL long long
struct Point
{
    int x,y;
    void read(){scanf("%d%d",&x,&y),x*=3,y*=3;}
    Point operator +(const Point &t)const{return {x+t.x,y+t.y};}
    Point operator -(const Point &t)const{return {x-t.x,y-t.y};}
    LL operator *(const Point &t)const{return 1ll*x*t.y-1ll*y*t.x;}
    Point operator *(const int &k)const{return {x*k,y*k};}
    Point operator /(const int &k)const{return {x/k,y/k};}
    bool operator ==(const Point &t)const{return x==t.x && y==t.y;}
    LL norm(){return 1ll*x*x+1ll*y*y;}
}G,A,B,C;
bool operator <(const Point &A,const Point &B)
{
    Point p1=A-G,p2=B-G;
    if(p1.x==0 && p1.y==0)return true;
    if(p2.x==0 && p2.y==0)return false;
    if(1ll*p1.y*p2.y<0)return p1.y>p2.y;
    LL Cr=p1*p2;
    if(Cr)return Cr>0;
    if(p1.y==0 && 1ll*p1.x*p2.x<0)return p1.x>p2.x;
    return p1.norm()<p2.norm();
}
set<Point>s;
typedef set<Point>::iterator cdx;
cdx pre(cdx it)
{
    if(it==s.begin())it=s.end();
    it--;return it;
}
cdx nxt(cdx it)
{
    ++it;
    if(it==s.end())it=s.begin();
    return it;
}
bool In(Point P)
{
    auto it=s.lower_bound(P);
    if(it==s.end())it=s.begin();
    LL Cr=(P-*pre(it))*(*it-P);
    if(Cr==0)return (P-*pre(it)).norm()<=(*it-*pre(it)).norm();
    return Cr<0;
}
void Ins(Point P)
{
    if(In(P))return;
    auto it=s.lower_bound(P);
    if(it==s.end())it=s.begin();
    s.insert(P);
    while(s.size()>3 && (*it-P)*(*nxt(it)-*it)<=0)
        s.erase(it),it=nxt(s.find(P));
    it=pre(s.find(P));
    while(s.size()>3 && (*pre(it)-*it)*(*it-P)<=0)
        s.erase(it),it=pre(s.find(P));
}
int q,o;
int main()
{
    scanf("%d",&q);
    q--,scanf("%d",&o),A.read();
    q--,scanf("%d",&o),B.read();
    q--,scanf("%d",&o),C.read();
    G=(A+B+C)/3;
    s.insert(A),s.insert(B),s.insert(C);
    while(q--){
        scanf("%d",&o),A.read();
        if(o==2)printf("%s\n",In(A)?"YES":"NO");
        else Ins(A);
    }
}