题面
两种操作:
1 往点集 S 中添加一个点(x,y);
2 询问 (x,y) 是否在点集 S 的凸包中. 数据保证至少有一个 2 操作, 保证刚开始会给出三个 1 操作, 且这三个操作中的点不共线.
题解
动态凸包板子
本来是习惯直接搞整个凸包的, 这里似乎得分别维护上下凸壳, 然后用平衡树来加点
话说没啥好说的...... 看代码啥都懂了......
- //minamoto
- #include<bits/stdc++.h>
- #define R register
- #define fi first
- #define se second
- #define IT map<int,int>::iterator
- #define pi pair<int,int>
- #define ll long long
- #define fp(i,a,b) for(R int i=a,I=b+1;i<I;++i)
- #define fd(i,a,b) for(R int i=a,I=b-1;i>I;--i)
- #define go(head,u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
- template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
- using namespace std;
- char buf[1<<21],*p1=buf,*p2=buf;
- inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
- int read(){
- R int res,f=1;R char ch;
- while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);
- for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');
- return res*f;
- }
- map<int,int>up,dw;
- int q,x,y,op;
- inline ll cross(pi a,pi b,pi c){return 1ll*(b.fi-a.fi)*(c.se-a.se)-1ll*(b.se-a.se)*(c.fi-a.fi);}
- bool ck(map<int,int> &mp,int x,int y){
- if(mp.empty())return false;
- if(mp.find(x)!=mp.end())return y>=mp[x];
- if(x<mp.begin()->fi||x>(--mp.end())->fi)return false;
- IT p=mp.lower_bound(x),q=p;--q;
- return cross(pi(x,y),*q,*p)>=0;
- }
- void ins(map<int,int> &mp,int x,int y){
- if(ck(mp,x,y))return;
- mp[x]=y;
- IT it=mp.upper_bound(x),itl=it;
- if(it!=mp.end()){
- ++itl;
- while(itl!=mp.end()&&cross(pi(x,y),*itl,*it)>=0)mp.erase(it),it=itl,++itl;
- }
- it=mp.lower_bound(x);IT itr=it;--itr;
- if(it==mp.begin()||itr==mp.begin())return;
- --it,--itr;
- while(it!=mp.begin()&&cross(pi(x,y),*it,*itr)>=0)mp.erase(it),it=itr,--itr;
- }
- int main(){
- // freopen("testdata.in","r",stdin);
- q=read();
- while(q--){
- op=read(),x=read(),y=read();
- if(op==1)ins(dw,x,y),ins(up,x,-y);
- else{
- bool fl1=ck(dw,x,y),fl2=ck(up,x,-y);
- puts((fl1&&fl2)?"YES":"NO");
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2935748.html