题目链接：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); } }