好久没发了
CDQ分治，具体做法见XHR的论文…
/**************************************************************
Problem: 2961
User: zhuohan123
Language: C++
Result: Accepted
Time:5060 ms
Memory:41704 kb
****************************************************************/ #include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const double eps=1e-,inf=1e12;
struct point
{
double x,y;
point(){x=y=;}
point(double X,double Y){x=X,y=Y;}
friend bool operator<(point a,point b)
{
if(abs(a.x-b.x)<eps)return a.y+eps<b.y;
else return a.x+eps<b.x;
}
};
inline point V(point s,point e){return point(e.x-s.x,e.y-s.y);}
inline double crossP(point a,point b){return a.x*b.y-b.x*a.y;}
inline double dotP(point a,point b){return a.x*b.x+a.y*b.y;}
struct T{int ispo;point o;}q[];
point t[];int tnum;
point up[];int unum;
point dw[];int dnum;
bool ans[];
void imerge(int l,int r)
{
if(l==r)return ;
int mid=(l+r)/;
imerge(l,mid);imerge(mid+,r);
tnum=;
for(int i=l;i<=mid;i++)
if(!q[i].ispo)t[++tnum]=q[i].o;
sort(t+,t+tnum+);
unum=;
for(int i=;i<=tnum;i++)
{
while(unum>&&crossP(V(up[unum-],up[unum]),V(up[unum],t[i]))>-eps)unum--;
up[++unum]=t[i];
}
up[unum+].x=up[unum].x+eps;up[unum+].y=-inf;
dnum=;
for(int i=tnum;i;i--)
{
while(dnum>&&crossP(V(dw[dnum-],dw[dnum]),V(dw[dnum],t[i]))>-eps)dnum--;
dw[++dnum]=t[i];
}
dw[dnum+].x=dw[dnum].x-eps;dw[dnum+].y=inf;
if(tnum!=)
for(int i=mid+;i<=r;i++)
if(q[i].ispo&&ans[i])
{
point near;
if(q[i].o.y<)
{
int L=,R=unum;
while(L<=R)
{
int Mid=(L+R)/;
if(dotP(q[i].o,V(up[Mid],up[Mid+]))>-eps)near=up[Mid],R=Mid-;
else L=Mid+;
}
}
else
{
int L=,R=dnum;
while(L<=R)
{
int Mid=(L+R)/;
if(dotP(q[i].o,V(dw[Mid+],dw[Mid]))<eps)near=dw[Mid],R=Mid-;
else L=Mid+;
}
}
if(*near.x*q[i].o.x+*near.y*q[i].o.y-q[i].o.x*q[i].o.x-q[i].o.y*q[i].o.y<eps)ans[i]=false;
}
}
int main(int argc, char *argv[])
{
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
int n;scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d%lf%lf",&q[i].ispo,&q[i].o.x,&q[i].o.y);
if(q[i].ispo)ans[i]=true;
}
for(int i=;i<=n&&q[i].ispo;i++)ans[i]=false;
imerge(,n);
for(int i=;i<=n;i++)
if(q[i].ispo)puts(ans[i]?"Yes":"No");
return ;
}